c++ - 任何人都可以建议以下代码的时间复杂度

Question

根据我的说法，时间复杂度应该是 O(nlogn)，因为外循环工作直到 n/2^k =1，内循环工作 n 次。谁能告诉我我的说法是否正确。

 while(n){ 
  j=n; 
  while(j>1){ 
    j-=1; 
  } 
  n/=2; 
} 

Answer 1

内层循环进行n次迭代，外层每次迭代将n除以2，因此有n + n/2 + n/4 + ... = 2n 内循环的总迭代次数和时间复杂度为 O(n)，而不是 O(n log n)。