java - 如何计算程序的 Big O 复杂度？

Question

我有一个大 O 符号问题。假设我有一个执行以下操作的 Java 程序:

1. 将一个整数数组读入一个 HashMap，它跟踪数组中存在的整数出现次数。 [1,2,3,1] 将是 [1->2, 2->1, 3->1]。

2. 然后我从 HashMap 中获取 Keys 并将它们放入 Array 中:

   Set<Integer> keys = dictionary.keySet();
   Integer[] keysToSort = new Integer[keys.size()];
   keys.toArray(keysToSort);
   

3. 使用 Arrays.sort 对 keyArray 进行排序。

4. 然后遍历排序后的keyArray，从HashMap中抓取相应的值，以显示或格式化结果。

我想我知道以下内容:

• 第 1 步是 O(n)
• 如果我相信 Java API，第 3 步是 O(n log n)

• 第 4 步是 O(n)

• 第 2 步:在进行此类计算时，我应该知道 Java 如何实现 Set 类 toArray 方法。我假设它遍历 HashMap 检索 Keys。如果是这样的话，我会假设它的 O(n)。

如果顺序操作要求我添加每个部分，那么最终计算将是 O(n + n·log n + n+n) = O(3n+n·log n)。

跳过常量，您有 O(n+n log n)。这可以进一步减少吗？还是我完全错了？

Answer 1

我相信 O(n + nlogn) 可以进一步简化为 O(nlogn)。这是因为 n 与 nlogn 相比逐渐变得微不足道，因为它们的复杂度不同。 nlogn 的阶数高于 n。这可以在 wikipedia page 上验证向下滚动到常用函数顺序部分。