Java Big-O性能

Question

我对我的课程项目的表现有疑问.

我通过阅读文本文件形成了大约5000个游戏对象.我有一个Treemap(称为supertree)作为其节点Treemaps(我猜的迷你树图).这些nodes/mini treemaps是动作,战略,冒险,运动,游戏标题等.基本上游戏类型和这些迷你树将持有游戏对象.所以它supertree本身可能会持有8个nodes/treemaps.

当我插入游戏对象时,它将确定mini tree它将进入哪里并将其放入其中.例如,如果我插入游戏超级马里奥世界,它将检查它是哪种类型,并看到它adventure,所以超级马里奥世界将被插入adventure树.

所以我的问题是如果问题列出了所有的表现会是什么action games,因为Treemap得到的是O(log n)

首先在超级树上寻找Action Node/Treemap,它将采用O(log n).

然后一旦进入内部Action treemap,它将获得o(n log n)正确的所有元素吗？

那么总的表现log n * (n * log n)是否正确？哪个比最差o(n).

[编辑]希望这有点澄清了我的帖子.

Answer 1

虽然supermap上的get是O(n_categories),但是通过另一个map(使用迭代器)应该是O(n_games).如果n_categories的上限为10(因为添加新游戏时类别的数量不会改变),您可以假设超图查找为O(1).

由于子图最多可以包含n_games条目(当所有条目都属于同一类别时),因此列出所有类型为action的游戏会为您提供O(n_games).不要忘记,为了迭代所有条目,您不必每次都调用get().这就像阅读一本书,而不是翻页从第100页到第101页,开始计数在开始计数到101​​ ...

编辑:由于上面的段落声明,如果类别的数量是固定的,人们可以假设类别查找是O(1)似乎很难接受,让我说,即使你坚持类别查找是O(log n_categories ),仍然给出O(n_games),因为类别查找只需要进行一次.然后,迭代结果,即O(n_games).这导致O(n_games + log n_categories)= O(n_games).