gpt4 book ai didi

java - 基数排序(java实现)复杂度

转载 作者:太空宇宙 更新时间:2023-11-04 13:55:22 29 4
gpt4 key购买 nike

这是我的第一个问题,所以我希望我没有违反任何规则。我终于设法为基数排序算法编写代码,但我想知道我是否做错了。让我觉得我的算法看起来复杂度为 O(n^3),但众所周知,基数排序是一个 O(k.n) 算法。我是否计算了算法的复杂性错误,或者我只是编写了非常糟糕的代码?

private static void radixSort(int[] A){
ArrayList<Integer>[] bucket = new ArrayList[10];
int maxNumberOfDigits = 0;
for(int number : A){
if(numberOfDigitsIn(number) > maxNumberOfDigits) maxNumberOfDigits = numberOfDigitsIn(number);
}
for(int c=0; c<bucket.length; c++){
bucket[c] = new ArrayList<Integer>();
}
int i = 0;
int digit;
int j;
while(i < maxNumberOfDigits){
for(j = 0; j<A.length; j++){
digit = getDigit(A[j], i);
bucket[digit].add(A[j]);
}

int index = 0;
for(int z = 0; z<bucket.length; z++){
for (int k=0; k<bucket[z].size(); k++){
A[index] = bucket[z].get(k);
index += 1;

}
bucket[z].clear();
}
i += 1;
}
}

方法 getDigit() 和 numberOfDigitsIn() 的时间是恒定的。

最佳答案

    for(int z = 0; z<bucket.length; z++){
for (int k=0; k<bucket[z].size(); k++){

这里的关键是所有桶大小的总和将等于 n,因此这些循环组合起来只需要 O(n)。 j 上的循环需要 O(n),i 上的 while 循环将运行 maxNumberOfDigits 迭代,该数字表示您描述的 O(kn) 运行时中的 k。所以总数实际上是 O(kn)。

关于java - 基数排序(java实现)复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/29883734/

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