Java的大O性能表现

Question

Java的大O性能表现

3

我有一个关于班级项目性能的问题。

我的项目有大约5000个游戏对象，这些对象是通过读取文本文件形成的。我有一个名为supertree的Treemap，它将其节点作为小型Treemaps（似乎是迷你树）。这些节点/小型Treemaps是动作、策略、冒险、体育、游戏标题等。基本上就是游戏类型，这些小树将容纳游戏对象。

因此，supertree本身可能会包含8个节点/Treemaps。

当我插入一个游戏对象时，它会确定它将进入哪个小树并将其放在那里。例如，如果我插入游戏Super Mario World，它将检查它属于哪种类型，并查看它是否为冒险游戏，所以Super Mario World将被插入到冒险树中。

我的问题是，如果问题列出所有动作游戏，性能如何，因为Treemap get是O(log n)。

首先，在超级树中，它将查找Action Node/Treemap，这需要O(log n)时间。

然后一旦进入Action Treemap，它将为所有元素执行get，这将是o(n log n)正确吗？

因此，log n * (n * log n)的总性能是正确的吗？这比o(n)更糟糕。

[编辑] 希望这能澄清我的帖子。

- criticalpath

编辑观点：在Stack Overflow上提出Big-O问题就像向早已熄灭的大学教育之火中倒油。 ;) - phooji

@user648727，您能否请详细说明一下您的树状图布局？超级地图包含多个类型，每个类型包含一个游戏对象的树状图/集合？ - phooji

4个回答

4

首先，你的大O表示法不会因语言的不同而改变；这就是人们使用大O（渐近）符号的原因。

现在，考虑整个算法。你获取你的外部树，并获得每个元素，这确实是O(n₀ lg n₀)。对于每个节点，你有O(n₁ lg n₁)。lg n只是一个常数差异，因此它们可以合并，你就得到了O(n_o×n₁ lg n)，或者O(n² lg n)。

- Charlie Martin

好的，我只是觉得既然我正在用Java编写我的项目并使用Java的TreeMap，那么我会在标题中加上Java。 - criticalpath

@Charlie Martin：我是一个有强迫症的理论计算机科学家。我不清楚你的各种n下标代表什么，以及最后的n_{no_subscript}从哪里来。请帮忙解释一下 :) - phooji

它代表着懒得严密地计算整个问题。你实际上需要一个n来表示超级树中节点的数量，以及每个子树的另一个n。因此，我（隐式地）假设每个子树的大小大致相同为n1，并且进一步假设n1/n0在某个常数值上有一个上界，因此渐近地n0 == n1。结论随之而来。 - Charlie Martin

感谢您使用内联HTML将SO转换为数学符号。我现在不完全清楚OP正在问什么。看起来您假设对树的两个级别进行了完整的遍历；我假设在外部树中进行单个查找，并在内部树中进行完整的遍历（而不计算任何级别的构建成本）。最后一个警告：请记住，遍历树的节点比重复元素查找更便宜（线性而不是O（n lg n））。 - phooji

是的，我是一个HTML专家；再也没有人让我写LaTeX了。但他的问题假设一系列gets，每个gets都是O(lg n)的。正如我们所指出的，这对于这个问题可能不是最优的--如果他使用了线程树，他可以在总节点上以线性时间列出所有Action节点，或者按照我上面的术语是O(n^2)，并完全消除对数项。 - Charlie Martin

2

关于楼主的分析，有几点评论：

我假设您已经构建了您的树状图/集合，并且只是从已完成的（预处理过的）内存表示中提取元素。

假设 n 是流派数量。假设 m 是每个流派的最大游戏数。

获取正确的“流派映射”的复杂度为O(lg n)（超级树的单个get）。在该流派中迭代游戏的复杂度取决于您如何执行：

 for (GameRef g : submap.keySet()) {
   // do something with supermap.get(g)
 }

这段代码产生O(m)的“获取”操作，每个操作的复杂度为O(lg m)，因此总共是O(m lg(m))。

如果您这样做：

for (Map.Entry e : submap.entrySet()) {
   // do something with e.getValue()
}

如果使用第一种方法，复杂度为O(m)，每次访问值的时间是常数级别的(O(1))。

使用第二种映射迭代方法，总复杂度为O(lg(n) + m)。

- phooji

旁注：正如@Axel在其他地方指出的那样，在这个演示中，如果您假设流派数量n受到常数限制，则最终结果变为O(1 + m) = O(m)。 - phooji

@Charlie Martin：我对现在树的实际布局和你一样感到困惑。短语：“当我插入一个游戏对象时，它会确定它将进入哪个“小树”并将其放入那里。”似乎表明超级树仅包含（少量）类型，而子树包含特定类型的游戏对象。 - phooji

如果我的问题措辞令人困惑，我深表歉意。我还没有编写实际项目，但我的计划是SuperTree可能会包含大约8个节点/树图（动作，冒险，策略，体育，射击等）。然后，当我插入一个实际的游戏，比如超级马里奥世界，它将检查它属于哪种类型，并看到它是冒险游戏，因此它将被插入到冒险树中。最初，我考虑只使用ArrayList或类似的东西，而列表动作游戏或任何其他类型的性能将为O(n)。也许我应该这样做？=/ - criticalpath

@user648727：这完全取决于你计划如何使用数据结构。如果我处在你的位置，我会先选择最容易编码的方式，然后再考虑性能问题。 - phooji

@jtn30769 哇，你知道的，针对你在这里谈论的规模，只需使用可能起作用的最简单的东西即可；更复杂的设置时间可能会支配其他一切。 - Charlie Martin

显示剩余4条评论

-1

嗯，你的观点一直到最后一段都是正确的。

你的总复杂度是 O(n logn)，logn 用于查找类型，n 用于列出该类型中的所有值。

如果你要列出所有内容，那肯定不是 O(n^2 logn)，因为获取树中所有值是线性的。它应该是 O(n^2)。

使用平面列表执行相同操作将是 O(n logn)，因此使用树会损失性能（更不用说内存）。

- Blindy

除非他对两者都使用相同的结构，否则没有理由它们都是线性时间。但我同意，树可能不是最好的选择。 - Charlie Martin

并不简单。大O表示最坏情况。如果您的地图中列出了所有动作游戏，则最坏情况为n，因为您的树中可能只有动作游戏，但在现实世界的场景中并非如此。每种游戏类型应该是n/GenreSize。因此，在现实世界中，如果他不希望所有游戏都在一棵树中，他应该使用TreeMaps。 - Plínio Pantaleão

为什么平面列表需要O(n log n)的时间复杂度？无论是使用列表还是树，列出所有内容都是O(n)，当迭代时，您会恰好访问每个节点，并且总共有n个节点。请记住，在遍历所有元素时，永远不会调用get方法-或者至少不应该这样做。 - Axel

@Plínio Pantaleão：Big-O符号大致意味着“函数增长的上限”，可用于描述最佳情况、最坏情况或平均情况下的运行时间。 - phooji

除了通常在算法分析中用于最坏情况的大O符号外，小o符号则用于最优情况。因此，当g(x)=O(f(x))时，表示在极限下g(x)/f(x)受到一个常数的限制，而当g(x)=o(f(x))时，则表示在极限下g(x)/f(x)趋近于0。 - Charlie Martin

显示剩余3条评论

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Axel · Accepted Answer

虽然超级地图的获取是O(n_categories)，通过其他地图（使用迭代器）遍历应该是O(n_games)。如果n_categories有一个上限，比如说10（因为添加新游戏时类别数量不会改变），则可以假定超级地图查找为O(1)。

由于子地图最多只能有n_games个条目（当所有条目属于同一类别时），列出所有类型为动作的游戏可得到O(n_games)。不要忘记，为了遍历所有条目，您不必每次都调用get()。这就像阅读一本书，从第100页到101页不必重新数一遍，而是翻过去即可。

编辑：既然上面一段话陈述如果类别数量固定，则可以假设类别查找为O(1)似乎难以接受，那么我来说一下，即使您坚持认为类别查找是O(log n_categories)，由于只需要进行一次类别查找，所以仍然得到O(n_games)的结果。然后，您遍历结果，这是O(n_games)。这导致O(n_games + log n_categories) = O(n_games)。