java - 为什么对数组进行排序/初始化不计入 Big O 中？

Question

我正在尝试找到问题的最有效答案(不使用 HashMap):查找数组中最常见的整数。

我得到的答案如下:

public int findPopular(int[] a) {

if (a == null || a.length == 0)
    return 0;

Arrays.sort(a);

int previous = a[0];
int popular = a[0];
int count = 1;
int maxCount = 1;

for (int i = 1; i < a.length; i++) {
    if (a[i] == previous)
        count++;
    else {
        if (count > maxCount) {
            popular = a[i-1];
            maxCount = count;
        }
        previous = a[i];
        count = 1;
    }
}

return count > maxCount ? a[a.length-1] : popular;

}

和

public class Mode {
public static int mode(final int[] n) {
    int maxKey = 0;
    int maxCounts = 0;

    int[] counts = new int[n.length];

    for (int i=0; i < n.length; i++) {
        counts[n[i]]++;
        if (maxCounts < counts[n[i]]) {
            maxCounts = counts[n[i]];
            maxKey = n[i];
        }
    }
    return maxKey;
}

public static void main(String[] args) {
    int[] n = new int[] { 3,7,4,1,3,8,9,3,7,1 };
    System.out.println(mode(n));
}
}

第一个代码片段声称是 O(n log n)。然而，单独的 Arrays.sort() 函数的复杂度是 O(n log n) [3]。如果添加 for 循环，findPopular() 函数不是 O(n^2 * log n) 吗？哪个会简化为 O(n^2)？

第二个代码 [2] 片段声称是 O(n)。但是，为什么我们不将数组的初始化考虑到我们的计算中呢？数组的初始化将花费 O(n) 时间 [4]，而 for 循环将花费 O(n) 时间。那么 mode() 函数不是 O(n^2) 吗？

如果我是正确的，那就意味着我还没有看到比 O(n^2) 更有效的答案。

一如既往，感谢您的帮助!

来源:

1. Find the most popular element in int[] array

2. Write a mode method in Java to find the most frequently occurring element in an array

3. The Running Time For Arrays.Sort Method in Java

4. Java: what's the big-O time of declaring an array of size n?

编辑:好吧，我觉得自己像个白痴。我会把这个留在这里，以防有人犯我同样的错误。

Answer 1

当您依次执行两项任务时，您会增加复杂性:

Arrays.sort(a); // O(n log n)
for (int i = 0; i < n; i++) { // O(n)
    System.out.println(a[i]);
}
// O(n log n + n) = O(n (log n + 1)) = O(n log n)

只有当你重复一个算法时，你才会相乘:

for (int i = 0; i < n; i++) { // O(n)
    Arrays.sort(a); // O(n log n), will be executed n times
}
// O((n log n) * n) = O(n² log n)