以下代码的大 O 是什么？

Question

代码：

int temp = 0;
for (int h = 1; h <= n; h = h * 2)
{
   for (int i = 1; i <= n; i++)
   {
      for (int j = 1; j<=n; j++)
      {
         for (int k = 1; k<i; k++)
         {
            temp++
         }
      }
   }
}

根据我的计算，big-O 是 lg n * n^4。请指导。

编辑：谢谢大家的回复。我明白我在哪里犯了错误。非常感谢大家的参与。

Answer 1

for (int h = 1; h <= n; h = h * 2) // increment is pow(2). hence executed ln(n) times
{
   for (int i = 1; i <= n; i++) // increment is one. Executed n times
   {
      for (int j = 1; j<=n; j++)// increment is one. Executed n times
      {
         // increment is one. Executed i times. See below
         for (int k = 1; k<i; k++)
         {
            temp++
         }
      }
   }
}

k 循环执行了 i 次。 i的最大值为n。所以你可以认为它总是被执行 n 次（过度近似）

复杂度 = ln(n) * n * n * n = ln*pow(n,3)

另一种看待它的方式...让我们交换 i 循环和 j 循环

for (int h = 1; h <= n; h = h * 2) // increment is pow(2). hence executed ln(n) times
    {
       for (int j = 1; j <= n; j++) // increment is one. Executed n times
       {
          // see below
          for (int i = 1; i<=n; i++)
          {
             for (int k = 1; k<i; k++)
             {
                temp++
             }
          }
       }
    }

现在看看....(i,k)的总执行次数是n*(n+1)/2。那么现在复杂度是多少？

h * j * (i,k) = ln(n) * n * (n*(n+1)/2) == ln(n) * pow(n,3)

Answer 2

只是为了好玩，我运行这段代码具有不同的 n 值：

               n                  temp               O?
     -----------        --------------        ---------
               1                     0
              10                  1800        1.8 x n^3
             100               3465000        3.5 x n^3
            1000            4995000000        5.0 x n^3
           10000         6999300000000        7.0 x n^3  (and took a LONG time!)

结论：log(n) * n^3

Answer 3

骑士基本上是对的，但是如果你想要正确的数字，你不能只说"I take the biggest value of i"。

是的，f(n) = O(...)是正确的，但你也可以写f(n) = O(n^15)，这也是正确的。

最后一个循环执行n次，然后n-1次，然后n-2次等等，即n+n-1+n-2+n-3....+3+2+1即n(n+1)/2。现在可以相乘得到n(n+1)/2 = n^2/2 + n/2，渐近运算可以忽略常量，也就是n^2/2 + n/2 = Theta(n^2+n)，也可以转化为n^2+n = Theta(n^2)

所以毕竟结果没有改变，但是你要确定。

最终结果如骑士所述n^3*log_2(n)

Answer 4

使用 Sigma 符号分析算法的复杂性

为了完整起见：在分析诸如算法中的嵌套和相互依赖循环的时间复杂度时，Sigma 表示法是一个很好的工具

其中 ⌊x⌋ 和 ⌈x⌉ 是 floor and ceiling functions.

从上面可以看出，算法的渐近行为的上限是 O(n^3 log_2(n))。

使用Sigma表示法估计实际迭代次数

Sigma 符号分析除了是 Big-O(-Ω, -Θ) 分析的严格工具外，如果我们有兴趣计算或估计 我们算法的迭代。

我们将估计的迭代次数（使用上面 ≤ 符号之前的公式）与@JohnHascell 的答案中给出的实际迭代次数进行比较。

// our formula (pseudo-code / matlab-compliant)
numIt(n) = n*ceil(log2(n))*(n^2-n)/2;

// comparison with actual count:
--------------------------------------------------------- 
           n     actual # of iter.   estimated # of iter. 
               (from @JohnHascell)   (from formula above)
------------   -------------------   --------------------
           1                     0                      0
          10                 1 800                  1 800
         100             3 465 000              3 465 000
        1000         4 995 000 000          4 995 000 000
       10000     6 999 300 000 000      6 999 300 000 000
---------------------------------------------------------

我们看到公式中的计数与实际计数完全吻合；在这种情况下，估计实际上是实际计数。

以下代码的大 O 是什么？

What will be the big-O of following code?

big-o

time-complexity

使用 Sigma 符号分析算法的复杂性