嵌套 While 循环的算法复杂度

Question

所以我在这个问题上遇到了一些麻烦，因为变量 i。我只是不确定在第二个 while 循环中如何处理它。对于我的外循环，我知道它将运行 log_4(n^2) 次迭代。对于内部 while 循环，我计算的迭代次数为 (2n^3 - 3)/i。我只是在努力研究如何将这两者放在一起以获得该功能的总体复杂性。非常感谢任何输入!

function p(n)
    i = 1;
    while i < n^2 do
        j = 3;
        while j < 2n^3 do
            j = j + i;
        end
        i = 4i;
    end

Answer 1

我不擅长数学，但我正在尝试回答这个问题。

首先让我们从第一次迭代开始计算:

• i=1:j增加了大约2n^3倍(分析复杂度时可以忽略常量)
• i=4: j增加了大约2n^3/4倍
• i=16:j增加了大约2n^3/16倍。
• ...
• i=n^2:j增加了大约2n^3/(n^2)倍。

总共j增加了: (2n^3)+(2n^3)/4+(2n^3)/16+(2n^3)/64+...+(2n^3)/(n^2) 次。 即:

2n^3*(1+1/4+1/16+1/64+1/256+...+1/(n^2))
= 2n^3((1-(1/4)^(log_4(n^2)))/(1-(1/4)))   // sum of geometric progression
= 2n^3 * (1-1/n^2) * 4/3

所以它是 O(n^3)。