-3

嵌套for循环的时间复杂度通过两个循环O（n2）复杂度的总和进入数学推导。

对于以下三个嵌套循环的示例，我尝试了一个练习来推导如何获得 O(n3)。

简单的三个嵌套循环。

   for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            for (int k = 1; k <= n; k++)
                 print(i * k * j);

求和是 = (n + n + n + .... + n) + (n + n + n + ... + n) + ... + (n + n + n + ... + n)

= n^2 + n^2 + .... + n^2

n 次 n^2 = O(n^3)

三个嵌套循环从一开始就没有运行 n 次

 for(int i = 1; i <= n; i++)
     for(int j = i; j <= n; j++)
         for(int k = j; k <= n; k++)
             print(i *j * k)

以上是嵌套循环的一种非常常见的形式，我相信总和如下

= (n + (n -1) + (n -2) + (n - 3) + ... + 1) + ((n -1) + (n - 2) + (n - 3) +.. . + 1) + ((n -2) + (n -3) + (n - 4) + ... + 1) + ... + ((n - (n -2)) + 1)

= n(n - 1) /2 + (n-1) (n -2) / 2 + (n-2)(n-3)/2 + .... + 1

= 从这里我有点不确定我的逻辑是否正确。我相信上面的每一个都评估为一个最大值为 n2 的多项式，因为这就是我们在时间复杂度上所关心的，所以上面的等式分解为。

= n^2 + n^2 + n^2 +... +n^2

= 这是 n 次 n^2 = O(n^3)。

我的假设正确吗？

三个嵌套循环未从末尾运行 n 次

for(int i = 1; i <= n; i++)
     for(int j = 1; j <= i; j++)
         for(int k = 1; k <= j; k++)
             print(i *j * k)

如果上面是两个嵌套循环，则总和将是 1 + 2 + 3 + 4 + ... + n。但是，对于三个嵌套的事件，我推断它是

= 1 + (1 + 2) + (1 + 2 + 3) + (1 + 2 + 3) + (1 + 2 + 3 + .... + n)

从这里我不确定如何推导出 O(n^3) 或如何进一步简化上述求和。

4

1 回答 1

1

使用事实： 1+2+3+...+i =i*(i+1)/2，上面的总和可以写成： 1*(1+1)/2 + 2*(2+1)/2 + ... + n*(n+1)/2。显然i*(i+1) > i^2，因此：

1*(1+1)/2 + 2*(2+1)/2 + ... + n*(n+1)/2 > (1^2+...+ n^2)/2， 据我们所知：

1^2+...+n^2 = n^3/3 + n^2/2 + n/6（可以通过归纳证明这一点）。

因此，原始总和S大于：

n^3/6 + n^2/4 + n/12，即O(n^3)。

于 2016-07-29T02:50:03.627 回答