大 O 表示法在代码中的解释

Question

我需要帮助理解代码中的大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(nlog(n))，而不是O(n^4)（错误）。

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(n^3log(n))(正确答案)。

- user3395013

---

将外层循环和内层循环相乘：n^(1/3) * n^3 = n^(3 + 1/3) - dan

请逻辑思考一下...如果内部循环像你所说的是n^3，为什么运行它n^(1/3)次会将其带到O(n)？如何嵌套循环并得出比仅拥有该循环更低的O()呢？ - Red Alert

所有人都说 j = 3*j 和 i = i/3 循环的复杂度是 O(n^3) 或 O(n^(1/3))。但这是错误的。在这两种情况下，它们的复杂度都是 O(log n)。 - David Knipe

另外，你的第一个例子不是O(n^4)，而是O(nlog(n))。我会把原因留给你作为练习，只需知道这与内部循环中j呈指数增长有关。 - Red Alert

好的，现在我有点困惑了。因为在这两种情况下都存在指数增长。那么它是O(log(n))吗？所以澄清一下，问题1：n*log(n)，因为n^3的增加。问题2：是O(log(n))，因为两个循环都是log(n)？ - user3395013

第一个值呈指数级增长，只需要 O(log N) 步骤即可完成，而另一个值则呈指数级下降，同样只需要 O(log N) 步骤即可完成。 - Nuclearman

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。

每个循环的大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，所以将两个循环的顺序相乘，我们得到：

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

- Joshua Kissoon

---

我的意思是代码的总体，但是根据评论，似乎对于这个问题的解读存在分歧？ - user3395013

哦，我通常从每个循环开始，并给循环一个顺序（O），您可以忽略单个语句。在为每个循环分配顺序后，从所有嵌套循环的顺序开始相乘，然后将所有顺序相加。我会更新问题以提供示例。 - Joshua Kissoon

我已更新答案，以给出一个示例，说明我如何阅读代码来确定复杂度。 - Joshua Kissoon

天啊，感谢您给我时间解释这个问题。我非常感激。 - user3395013

欢迎您，希望您能回馈社区，许多人需要帮助。欢迎来到StackOverflow ;)。 - Joshua Kissoon

Answer 2

在第一个代码块中，您正确编写了第一个for循环，但未正确编写第二个for循环。在第二个for循环中，j呈指数增长，即j = 1,3,9,27...
因此，时间随着结束值的对数增加而增加。让我们看一个例子，基于这行代码。

for ( j = 1; j < m; j = 3*j )

这是一个关于m、j和时间数值的表格：

m     j        time
1     -         0       // body of loop never executes   
3     1         1       // body of loop executes one time  
9     1,3       2     
27    1,3,9     3  
81    1,3,9,27  4  

所以在这种情况下，时间复杂度为log_base_3( m )，用大O符号表示就是O(log m)。如果你用n^3替换m，那么时间复杂度就是3 * log_base_3( n )，实际上只是O(log n)，因为大O符号忽略常数乘数。总之，第一个块的解决方案是O(n*log(n))。

另一个块可以用类似的方式进行分析。

- user3386109