这个伪代码的复杂度（Ø）是多少？
What is the complexity(Ø) of this pseudo code?
我的问题是关于找出这个算法的复杂性。 J值与n有关，所以我对此感到困惑。
这个伪代码的渐近复杂度是多少？
for i=1 to n
do
j = 1;
while (j < n)
do
j = j * 2;
谢谢。
我相信是 O(n log<sub>2</sub>n)
外循环被调用 n 次，内循环被调用 log<sub>2</sub>n 次，因为在每个迭代，j 加倍。对于第一次迭代，即 k=0； j 等于 1 并继续像 2, 4, 8, ... 直到 2<sup>k</sup>>=n
如果我在内部循环的末尾添加打印，我会看到：
(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)
我的问题是关于找出这个算法的复杂性。 J值与n有关，所以我对此感到困惑。
这个伪代码的渐近复杂度是多少？
for i=1 to n
do
j = 1;
while (j < n)
do
j = j * 2;
谢谢。
我相信是 O(n log<sub>2</sub>n)
外循环被调用 n 次，内循环被调用 log<sub>2</sub>n 次，因为在每个迭代，j 加倍。对于第一次迭代，即 k=0； j 等于 1 并继续像 2, 4, 8, ... 直到 2<sup>k</sup>>=n
如果我在内部循环的末尾添加打印，我会看到：
(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)