gpt4 book ai didi

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

转载 作者:行者123 更新时间:2023-12-01 12:37:19 26 4
gpt4 key购买 nike

我正在尝试找到问题的最有效答案(不使用 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?

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

最佳答案

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

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)

关于java - 为什么对数组进行排序/初始化不计入 Big O 中?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/25473044/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com