Java Big-O 性能

Question

我对我的课堂项目的表现有疑问。

我有大约 5000 个通过读取文本文件形成的游戏对象。我有一个 Treemap （称为超级树），它作为其节点 Treemaps （我猜是迷你树图）。这些节点/迷你树图是动作、策略、冒险、体育、游戏标题等。基本上是游戏类型，这些迷你树将保存游戏对象。因此，supertree 本身可能会容纳 8 个节点/树图。

当我插入游戏对象时，它将确定它将转到哪个迷你树并将其放入其中。例如，如果我插入游戏超级马里奥世界，它会检查它是什么类型，并发现它是冒险，所以超级马里奥世界会被插入到冒险树中。

所以我的问题是，如果问题列出所有动作游戏，性能会怎样，因为树图获取的时间复杂度为 O(log n)

首先，它将在超级树中查找动作节点/Treemap，这将需要 O(log n)。

然后，一旦进入 Action 树形图，它将获取所有元素，这将是 o(n log n) 正确的吗？

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

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

Answer 1

虽然获取超级地图的时间复杂度为 O(n_categories)，但遍历另一个地图（使用迭代器）应该为 O(n_games)。如果 n_categories 的上限为 10（因为添加新游戏时类别数量不会改变），则可以假设 supermap 查找为 O(1)。

由于子地图最多可以有 n_games 个条目（当所有条目都属于同一类别时），因此列出所有动作类型的游戏将为您提供 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)。

Answer 2

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

现在，考虑一下你的整个算法。您获取外部树并获取每个元素，这确实是O(n₀ lg n₀)。对于每个节点，您都有 O(n₁ lg n₁)。 lg n 仅相差一个常数，因此可以将它们组合起来，得到 O(n_o×n₁ lg n)，或 O(n² lg n)。

Answer 3

关于OP分析的一些评论：

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

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

获取正确的“流派地图”的复杂度是O(lg n)（超级树的单个get）。迭代该类型游戏的复杂性取决于您的操作方式：

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

此代码会产生 O(m) 复杂度为 O(lg m) 的“get”操作，所以这是 O(m lg(m))。

如果这样做：

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

那么复杂性是 O(m) 循环迭代，并且访问该值的时间为常量 (O(1)) 次。

使用第二种地图迭代方法，您的总复杂度为 O(lg(n) + m)

Answer 4

呃，直到最后一段你都是对的。

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

如果您正在讨论列出所有内容，那么它绝对不是 O(n^2 logn)，因为获取树中的所有值是线性的。这将是O(n^2)。

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