我的问题是关于找到这个算法的复杂性 J 值与 n 有关，所以我对此感到困惑。
这个伪代码的渐近复杂性是什么？
for i=1 to n
do
j = 1;
while (j < n)
do
j = j * 2;
谢谢
1
我相信是O(n log2n)
外部循环被调用n次，内部循环被调用log2n次，因为在每次迭代中，j都加倍。对于第一次迭代，即k=0;j等于1，并像2, 4, 8, ...一样持续到2k>=n
-2
如果我在内部循环的末尾添加打印，我看到：
(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)
本站系公益性非盈利分享网址，本文来自用户投稿，不代表边看边学立场，如若转载，请注明出处
评论列表（24条）