以下代码的复杂度是多少,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)。