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

Question

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

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

2. 然后我从中抓取钥匙HashMap并将它们放在Array:

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

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

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.这可以通过向下滚动到"常用功能顺序"部分在维基百科页面上进行验证.