2

我正在练习 Skiena 的算法书，我陷入了这个问题：

我需要计算以下算法的大 O：

      function mystery()
      r=0
      for i=1 to n-1 do
         for j=i+1 to n do
            for k=1 to j do
                r=r+1

在这里，最外层循环的大 O 为 O(n-1)，中间循环为 O(n!)。如果我在这里错了，请告诉我。

我无法计算最内层循环的大 O。

谁能帮我解决这个问题？

4

3 回答 3

2

这是解决此问题的更严格的方法：

将算法的运行时间定义为f(n)因为n是我们唯一的输入。外循环告诉我们这一点

f(n) = Sum(g(i,n), 1, n-1)

从到Sum(expression, min, max)的总和在哪里。请注意，在这种情况下，表达式是具有固定（总和索引）和（输入）的评估。我们可以剥离另一层并定义：expressioni = mini = maxg(i, n)inf(n)g(i, n)

g(i, n) = Sum(h(j), i+1, n), where i < n

这是 到 的h(j)wherej范围之i+1和n。最后我们可以定义

h(j) = Sum(O(1), 1, j)

因为我们假设这r = r+1需要时间O(1)。

请注意，此时我们没有做任何挥手，说诸如“哦，你可以将循环相乘。'最里面的操作'是唯一重要的。” 这种说法甚至不适用于所有算法。这是一个例子：

for (i = 0; i < n; i++)
{
    for (j = 0; j < n; j++)
    {
        Solve_An_NP_Complete_Problem(n);
        for (k = 0; k < n; k++)
        {
            count++;
        }
    }
}

上面的算法不是O(n^3)……它甚至不是多项式的。

无论如何，既然我已经确定了严格评估的优越性（：D），我们需要向上工作，这样我们才能弄清楚上限是什么f(n)。首先，很容易看出h(j)是O(j)（只需使用 Big-Oh 的定义）。由此我们现在可以重写g(i, n)为：

g(i, n) = Sum(O(j), i+1, n)
=> g(i, n) = O(i+1) + O(i+2) + ... O(n-1) + O(n)
=> g(i, n) = O(n^2 - i^2 - 2i - 1) (because we can sum Big-Oh functions 
                                    in this way using lemmas based on 
                                    the definition of Big-Oh) 
=> g(i, n) = O(n^2) (because g(i, n) is only defined for i < n. Also, note
                     that before this step we had a Theta bound, which is 
                     stronger!)

所以我们可以重写f(n)为：

f(n) = Sum(O(n^2), 1, n-1)
=> f(n) = (n-1)*O(n^2) 
=> f(n) = O(n^3)

您可能会考虑证明下界以表明f(n) = Theta(n^3). 诀窍是注意简化g(i, n) = O(n^2)但在计算时保持严格的界限f(n)。它需要一些丑陋的代数，但我很确定（即我实际上没有做过）你也能够证明f(n) = Omega(n^3)（或者Theta(n^3)如果你真的很细致，就直接证明）。

于 2013-09-10T05:20:15.563 回答
2

分析如下：

  • 外循环从 开始，因此如果在此循环内仅执行恒定操作，i = [1, n - 1]则程序将具有线性复杂度 ；O(i) = O(n)
  • 然而，在第一个循环中，对于每个i，一些操作被执行了n几次——从j = [i + 1, n - 1]. 这给出了总复杂度O(i * j) = O(n * n) = O(n^2)；
  • 最后，最里面的循环将被执行，对于 each i，对于 each j，k时间，k范围从k = [j, n - 1]. 以j开头i + 1 = 1 + 1,k渐近等于n, 这给了你O(i * j * k) = O(n * n * n) = O(n^3).

程序本身的复杂度对应于你最里面的操作的迭代次数——或者最里面的操作的复杂度的总和。如果你有：

for i = 1:n

    for j = 1:n

        --> innermost operation (executed n^2 times)

        for k = 1:n
            --> innermost operation (executed n^3 times)
        endfor

        for l = 1:n
            --> innermost operation (executed n^3 times)
        endfor

    endfor

endfor

总复杂度为O(n^2) + O(n^3) + O(n^3)，等于max(O(n^2), O(n^3), O(n^3))或O(n^3)。

于 2013-09-10T03:31:06.253 回答
1

它不能是阶乘。例如，如果你有两个嵌套循环，那么大 O 将是 n^2，而不是 n^n。所以三个循环不能超过 n^3。继续挖掘；）

于 2013-09-10T02:58:36.280 回答