计算这些算法的大O复杂度？

Question

我想弄清楚以下2种算法的大O符号，但我遇到了麻烦。

第一个是：

public static int fragment3 (int n){ 
int sum = 0; 
for (int i = 1; i <= n*n; i *= 4) 
    for (int j = 0; j < i*i; j++) 
    sum++; 
    return sum; 
} //end fragment 3 

答案应该是O(n^4)。当我尝试自己做这件事时，我得到： 我看着第一个循环，并认为它运行n^2登录次。然后对于内循环，它运行n次+外循环的运行时间为n^3 logn次。我知道这是错误的，但不明白。

对于下面的代码片段，答案是O(n^9)。

public static int fragment6(int n) { 
int sum = 0; 
for(int i=0; i < n*n*n; i++) { 
    if(i%100 == 0) { 
    for(int j=0; j < i*i; j += 10) 
     sum++; 
    } // if 
    else { 
    for(int k=0; k <= i; k++) 
     sum++; 
    } // else 
} // outer loop 

return sum; 
} // fragment 6 

当我尝试它，我得到：n^3对于外部for循环。对于if语句，我得到n，对于第二个循环，我得到n +另一个for循环和if语句，使其成为n^5。最后，我得到n为最后的循环，一切都加起来O(n^6)。

我在做什么错，什么是正确的方法来获得其复杂性？

Answer 1

第一种情况：内环的，其中i

• 最后运行= N^2，运行对于n^4。外循环达到n^2，但使用指数增长。总结所有内循环运行的总和，但最后一个小于最后一次运行。所以内循环本质上是贡献O（1）。

第二种情况：

• 100％N == 0并不重要，真正为O思维
• 其他部分没有关系，它比主要部分
• 外环少得多运行从0到n^3 => N R个3
• 内环从0到n^6 => N R个6
• 外环倍内环=> N R个9

Answer 2

你的计算big-O的方法是错误的，并且你犯了计算错误。

在某些普通情况下可以采取迭代的最坏情况数目和它们相乘，但这不是一个有效方法，并为失败的情况下是这样的：

for (i = 1; i < n; i *= 2) { 
    for (j = 0; j < i; j++) { 
     sum++; 
    } 
} 

这里，外部循环运行log_2（n）次，内循环最坏情况是n次迭代。所以你使用的错误方法会告诉你这个代码的复杂性是O（n log n）。

正确的方法是准确计算迭代的次数，并且只在最后进行近似。迭代的次数实际上是：

1 + 2 + 4 + 8 + ... + 2^k 

其中2^k是两个最大功率小于n。这个总和是2 ^（k + 1） - 1，小于2n。所以准确的复杂度是O（n）。

将这一想法告诉第一个例子：

for (int i = 1; i <= n*n; i *= 4) 
    for (int j = 0; j < i*i; j++) 
     sum++ 

i取值为4^0, 4^1, 4^2, ..., 4^k其中4^k是小于4或等于n^2最大功率。

对于给定的值i，内循环执行i^2次。

所以，总体来说，内sum++执行很多次：

(4^0)^2 + (4^1)^2 + ... + (4^k)^2 
= 2^0 + 4^2 + ... + 4^2k 
= 16^0 + 16^1 + ... + 16^k 
= (16^k - 1)/15 

现在由k定义，我们有n^2/4 < 4^k <= n^2。所以n^4/16 < 4^2k <= n^4，以及从16^k = 4^2k，我们得到内循环执行的总次数为O（16^k）= O（n^4）。

第二个例子可以使用类似的方法解决。

Answer 3

第一个。

让我们看一下内环..

在外环（I = 1）的第一次迭代运行一次。在第二次迭代中（i = 4）它运行16（4 * 4）次。在第三次迭代中（i = 16），它运行256（16 * 16）次。通常，在外循环内环的第（k + 1）次迭代处运行次，如在该迭代处的。因此迭代的总数将

现在，如何在和很多数字，我们将有？确定我们应该看看外部循环。其中我成长为，直到它达到。所以迭代的总次数是。

这意味着内部循环的运行的总数是

（通过从总和但最后一个丢弃所有的数字）。

现在我们知道，内循环运行至少次，所以我们不会比O（n^4）更快。

现在，

求解N，

其中C是一个常数，所以我们不为O慢（N^4）。