algorithm - Big O on code的解释

Question

我需要一些帮助来理解代码中的 Big O 概念。我们只讨论了 30 分钟，没有讨论如何在 Java 上解释代码(我认为？)。任何人，我会尝试尝试我的解决方案，你们能告诉我我是对还是错，并给我一个适当的解释吗？

谢谢!

 sum = 0 ;
    for ( i = 0 ; i < n ; i++ ) --> n
        for ( j = 1 ; j < n^3 ; j = 3*j ) --> n*(3n^3) (WRONG) --> log(n)
            sum++ ;

因此这个上的大 O 是 O(n^4)(错误)正确答案 = O(nlog(n))

sum = 0 ;
for ( i = n ; i > 0; i = i/3 ) --> n^(1/3) (WRONG) --> log(n)
    for ( j = 0 ; j < n^3 ; j++ )--> n^(1/3) * (n^3)
       sum++ ;

因此这个上的大 O 是 O(n)(WRONG)正确答案 = O(n^3log(n))

Answer 1

对于你的第一个例子:

sum = 0 ;
for ( i = 0 ; i < n ; i++ ) --> n
   for ( j = 1 ; j < n^3 ; j = 3*j ) --> O(log n)
        sum++ ;

第二个循环将是 logn，因为我们每次都将 j 乘以因子 3，所以顺序将是 O(n logn) 而不是 n^4

每个循环的 Big O 计算都是正确的，但是，如果循环中有循环，则将计算相乘。

sum = 0 ;
for ( i = n ; i > 0; i = i/3 ) --> log n
    for ( j = 0 ; j < n^3 ; j++ )--> n^3
       sum++ ;

这里的第一个循环也将是 log n，因为你不断地除以 3，所以乘以我们得到的 2 个循环的顺序:

O(logn * n^3) = O(n^3 logn)

我们不能进一步减少它，因为我们没有要删除的常量。

只是指出我们对这种情况的一个简单误解，通常如果我们有以下情况，我们可以将其简化为

O(n^3 + n^2) = O(n3)

但是，您的场景不是订单的加法，而是乘法，因此我们不能再次删除此处的 O(logn)。

如何分析代码:

我是这样做的，举个例子

for(i=0; i < n; i++)
    for(j=0; j < n*2; j++)
for(k=0; k<n; k++)
    for(l=0; l<n; l+=3)
        for(m=0; m<n; m*=2)

首先，为每个循环找到大 0:

for(i=0; i < n; i++)        --> O(n)
    for(j=0; j < n*2; j++)  --> 2n = O(n)
for(k=0; k<n; k++)          --> O(n)
    for(l=0; l<n; l+=3)     --> n/3 = O(n)
        for(m=0; m<n; m*=2)  --> O(log n)

将外循环乘以内循环:

for(i=0; i < n; i++)        --> O(n) * O(n) = O(n^2)
    for(j=0; j < n*2; j++)  --> 2n = O(n)
for(k=0; k<n; k++)          --> O(n) * O(n) * (log n) = O(n^2 (log n))
    for(l=0; l<n; l+=3)     --> n/3 = O(n)
        for(m=0; m<n; m*=2)  --> O(log n)

现在我们加上外层循环的顺序，所以我们得到:

O(n^2) + O(n^2 log n) = O(n^2 + n^2 (logn))

然后我们减少订单。在这种情况下，n^2 log n 的增长率大于 n^2，因此我们可以删除 n^2，因为 n^2 logn 足以解释增长率。所以最后，我们有:

O(n^2 (log n))