algorithm - 条件变化时嵌套 while 的时间复杂度

Question

我正在尝试解决这个循环的复杂性

for(int i= 0; i < n; i++) {    
 c = i;    
 while(c > 1){     
  O(1);     
  c = c / 2;     
 }    
}

随着 while 条件在每个循环中发生变化，我不知道如何计算那个奇怪的序列。

我的意思是，如果循环在哪里

for(int i= 0; i < n; i++) {     
 c = n;     
 while(c > 1){     
  O(1);     
  c = c / 2;     
 }
}

我知道 while 的复杂度是 O(logn)，并且它会重复 n 次，所以复杂度是 O(nlogn)。

我之前的循环遇到的问题是“c=i”。当c = i时，第一次(c = 0)循环将重现0次，当c = 1时，它将再次重现0次，当c = 2时，它将重现1次，然后系列将随之而来，并且为0， 0, 1, 2, 2, 3, 3...(每次for循环时复制)

O(logn)不会重复本身n次，会重复很多次我想不出，所以我不知道如何解决它。

Answer 1

这需要一些数学知识。鉴于 a 和 b 的对数定义良好:

log(a) + log(b) = log(ab)

这里有

log(1) + log(2) +....+ log(n) = log(1*....*n) = log(n!)

有一个mathematical approximation对于 log(n!)，即

 log(n!) ~ nlog(n) - n + 1

揭示O(log(n!)= O(nlog(n))