嵌套 While 循环的算法复杂性

因此，由于变量 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

最佳答案

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

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

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)。

关于嵌套 While 循环的算法复杂性，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/33207379/

2N

嵌套 While 循环的算法复杂性