嵌套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）。

Answer 2

对于内部循环，存在一种情况，其中i = 1，一旦开始。 对于i = 1，内部循环有大约2n^3次迭代，我们可以说第一次外部循环的复杂度是O（n^3）。

请注意，由于我们试图计算复杂性，我将摆脱常数和系数。那么，对于i的其他值，内循环的迭代次数约为n^3/i。所以，当我增长时，迭代的次数会急剧减少。最后，对于i〜= n^2的最后一个值，它将是n。

所以，现在，我们有一个像n^3 + ..... + n，这给了我们总的复杂性。 这个总和中的术语数是log_4（n^2）= 2log_4（n），比如log_4（n）。

通常，我们知道n^3 + n^2 + n与n^3相同。但问题是我们在这种情况下可以想到同样的情况吗？因为在这种情况下，有更多的术语和术语数取决于n。让我们来看看。

即使所有术语都是n^3种类，结果也会是log_4（n）* n^3。 但是在本系列中，其他条款的几何下降值不会保持n^3。另外log_4（n）对于人们通常使用的大量数字来说是非常小的值。实际上，人们不能简单地忽略它，但是当我们一起考虑它是一个小数字和其他术语“急剧下降;你可以忽略log_4（n）和我们可以说复杂度是O（n^3）。

这不是一个确切的数学解决方案，但为了方便您，我们可以使用这种估算方法，如果您确定我们正在做什么。这就是我的观点，为什么我要这样解释。

如果你正在寻找更具体的东西，你可以说它介于O（n^3）和O（log_4（n）* n^3）之间。

此外，我已经计算了一些不同n值的实验值。您可以看到数字在代码中的行为，以及迭代次数与n^3之间的关系。以下是结果：

Test #1: 
n: 15 
n^2: 225, n^3: 3375 
...i=1, added 3375 iterations 
...i=4, added 843 iterations 
...i=16, added 210 iterations 
...i=64, added 52 iterations 
Total # of iterations for this test case: 4480 

Test #2: 
n: 56 
n^2: 3136, n^3: 175616 
...i=1, added 175616 iterations 
...i=4, added 43904 iterations 
...i=16, added 10976 iterations 
...i=64, added 2744 iterations 
...i=256, added 686 iterations 
...i=1024, added 171 iterations 
Total # of iterations for this test case: 234097 

Test #3: 
n: 136 
n^2: 18496, n^3: 2515456 
...i=1, added 2515456 iterations 
...i=4, added 628864 iterations 
...i=16, added 157216 iterations 
...i=64, added 39304 iterations 
...i=256, added 9826 iterations 
...i=1024, added 2456 iterations 
...i=4096, added 614 iterations 
...i=16384, added 153 iterations 
Total # of iterations for this test case: 3353889 

Test #4: 
n: 678 
n^2: 459684, n^3: 311665752 
...i=1, added 311665752 iterations 
...i=4, added 77916438 iterations 
...i=16, added 19479109 iterations 
...i=64, added 4869777 iterations 
...i=256, added 1217444 iterations 
...i=1024, added 304361 iterations 
...i=4096, added 76090 iterations 
...i=16384, added 19022 iterations 
...i=65536, added 4755 iterations 
...i=262144, added 1188 iterations 
Total # of iterations for this test case: 415553936 

Test #5: 
n: 2077 
n^2: 4313929, n^3: 8960030533 
...i=1, added 8960030533 iterations 
...i=4, added 2240007633 iterations 
...i=16, added 560001908 iterations 
...i=64, added 140000477 iterations 
...i=256, added 35000119 iterations 
...i=1024, added 8750029 iterations 
...i=4096, added 2187507 iterations 
...i=16384, added 546876 iterations 
...i=65536, added 136719 iterations 
...i=262144, added 34179 iterations 
...i=1048576, added 8544 iterations 
...i=4194304, added 2136 iterations 
Total # of iterations for this test case: 11946706660 

Test #6: 
n: 5601 
n^2: 31371201, n^3: 175710096801 
...i=1, added 175710096801 iterations 
...i=4, added 43927524200 iterations 
...i=16, added 10981881050 iterations 
...i=64, added 2745470262 iterations 
...i=256, added 686367565 iterations 
...i=1024, added 171591891 iterations 
...i=4096, added 42897972 iterations 
...i=16384, added 10724493 iterations 
...i=65536, added 2681123 iterations 
...i=262144, added 670280 iterations 
...i=1048576, added 167570 iterations 
...i=4194304, added 41892 iterations 
...i=16777216, added 10473 iterations 
Total # of iterations for this test case: 234280125572 

Test #7: 
n: 11980 
n^2: 143520400, n^3: 1719374392000 
...i=1, added 1719374392000 iterations 
...i=4, added 429843598000 iterations 
...i=16, added 107460899500 iterations 
...i=64, added 26865224875 iterations 
...i=256, added 6716306218 iterations 
...i=1024, added 1679076554 iterations 
...i=4096, added 419769138 iterations 
...i=16384, added 104942284 iterations 
...i=65536, added 26235571 iterations 
...i=262144, added 6558892 iterations 
...i=1048576, added 1639723 iterations 
...i=4194304, added 409930 iterations 
...i=16777216, added 102482 iterations 
...i=67108864, added 25620 iterations 
Total # of iterations for this test case: 2292499180787