algorithm - 这段代码的大O

Question

我正在做 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。

谁能帮我解决这个问题？

Answer 1

这里有一个更严格的方法来解决这个问题:

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

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

其中 Sum(expression, min, max) 是 expression 从 i = min 到 i = max< 的总和。请注意，在这种情况下，表达式是对 g(i, n) 的评估，具有固定的 i(求和索引)和 n (f(n) 的输入)。我们可以剥离另一层并定义g(i, n):

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

它是 h(j) 的总和，其中 j 范围是 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) 如果你真的很细心的话)。