计算以下算法的复杂度？
这个问题在这里已经有了答案：
i = 1;
while(i < n + 1){
j = 1;
While(j < n + 1){
j = j * 2:
}
i = i + 1;
}
外循环需要O（n），因为它按常量递增。
i = 1;
while(i < n + 1){
i = i + 1;
}
内循环：j = 1,2,4,8,16，...，2 ^ k
j = 2 ^ k（k> = 0）何时j将停止？
当j == n时，
log（2 ^ k）= log（n）
=> k * lg（2）= lg（n）..... so k = lg（n）。
While(j < n + 1){
j = j * 2;
}
所以总O（n * lg（n））
由于j指数规律增长，因此内部循环取O(log(n)) 。
由于i线性增长，外部循环需要O(n) 。
因此总的复杂度是O(n*log(n)) 。
这个与以下代码类似：
for( int i = 1;i < n+1 ; i++){ // this loop runs n times
for(int j = 1 ; j<n+1 ; j=j*2){// this loop runs log_2(n)(log base 2 because it grows exponentially with 2)
//body
}
}
因此，在Big-Oh表示法中，它是O（n）* O（logn）; 即O（n * logn）
链接地址: http://www.djcxy.com/p/39345.html