原地桶排序的算法复杂度分析的疑问,该怎么处理

原地桶排序的算法复杂度分析的疑问
如下一段代码对一个数组做原地桶排序，请大家帮忙分析下其算法复杂度是O（N）还是O（N2）？内层while循环的算法复杂度如何分析？

C/C++ code

#include <iostream>using namespace std;int main(){    int a[10] = {3,2,4,9,6,1,0,8,7,-1};    int temp;    int temp_val;    for(int i = 0; i < 10; i++){        if(a[i] != i){            temp_val = temp = a[a[i]];//临时变量先存储需要更换的值            a[a[i]] = a[i];            a[i] = temp;            }        while(a[temp_val] != temp_val){            temp = a[temp_val];            a[temp_val] = temp_val;            temp_val = temp;            if(temp_val == -1) break;        }    }    for(int j = 0; j < 10; j++){        cout<<a[j]<<endl;        if(a[j] != j) cout<<"the miss number is"<<j<<endl;    }    return 0;}

[解决办法]
内层while（貌似其实完全把if和while合并）每执行一次保证能把一个数据挪到正确的位置，所以这个肯定是O(N)。另一个角度说这个执行次数必然小于10次if加10次while。没太仔细看，不过这个程序感觉对-1的判断有点问题
[解决办法]

探讨

引用:

N*O(1)+N*N
首先肯定是大于O(N)，关键看你while的上界，最坏情况下你的while要执行N次，所以是N*N


照这么算很多O(N)的算法都要变O(N^2)了

[解决办法]
这个最坏就是O(N)，每次if或者while循环都能保证把一个元素移动到正确位置，而对于位置正确的元素if和while循环体都不会执行，所以if和while循环体合起来的执行次数不会大于N。
[解决办法]
如果第一次循环，while执行了N-1此，那以后每次循环while都不可能再执行了。while的执行条件是发现位置不对的元素，而这种事最多只能发生N次。

比如书有10页，页码从1到10，那所有页码加起来应该是55，如果算出来时50，那么就是第5页没了。当然这个前提是只缺了一页

查看更多 下一篇