外环线性,内环对数,复杂度分析

问题描述 投票:0回答:0

以下代码的复杂度是多少,O(logn) 或 O(nlogn)?

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

我问了 chatgpt,有时它说 O(logn),有时说 O(nlogn)。 O(logn) 的论据是内层循环支配迭代次数,应该采用,而 O(nlogn) 的论据(我觉得更合理)是这是从 1 到的对数之和n,也就是logn!,可以近似为O(nlogn)。我还看到了this stackoverflow 问题,其中一个答案是 O(nlogn),另一个是 O(logn)。

time-complexity big-o complexity-theory
© www.soinside.com 2019 - 2024. All rights reserved.