这个伪代码的复杂性(Ø)是多少？

Question

我的问题是关于找到这个算法的复杂性。J值与n相关，所以我很困惑

这个伪代码的渐近复杂度是多少?

for i=1 to n
do
j = 1;
while (j < n)
do
j = j * 2;

谢谢。

Answer 1

我相信是O(n log2n)

外循环称为n次，内循环称为log2n次，因为在每次迭代中，j被加倍。对于第一次迭代，即k=0;j等于1，像2, 4, 8, ...一样，直到2k>=n

Answer 2

如果我在内循环的末尾添加一个print，我看到:

(1,2,5)
(1,4,5)
(1,8,5)
(2,2,5)
(2,4,5)
(2,8,5)
(3,2,5)
(3,4,5)
(3,8,5)
(4,2,5)
(4,4,5)
(4,8,5)
(5,2,5)
(5,4,5)
(5,8,5)

所以它看起来是O(n^2)但内部循环看起来是常数所以可能是O(n) -如果(j < n)部分切换到(j < i)，那将更接近于O(n log(n)):

(2,2,5)
(3,2,5)
(3,4,5)
(4,2,5)
(4,4,5)
(5,2,5)
(5,4,5)
(5,8,5)