algorithm - 这些谜题的运行时间是多少？

Question

mystery(int A[1..n], int n) { 
        // pre: n is a power of 2 for i=1..n {
        for i = 1...n {
            A[i] = A[i] + 1; 
        }
        if (n>1) mystery(A, n/2);
    }

}

我认为最坏的情况，它在 O(n) 内运行，对吗？

---

编辑:这是来自另一个旧考试(它为我们提供了答案)，但以下算法在 O(n*log n) 时间内运行(根据答案)。为什么这样？我认为这两者应该仅相差一些常量。

void silly (int n)
    if (n>1)
        for (int i=0; i<n; i++)
            output "looping for fun"
        silly(n/2)
        for (int i=0; i<n; i++)
            output "looping for more fun"
        silly(n/2)
        for (int i=0; i<n; i++)
            output "looping for even more fun"

Answer 1

是的，它是 O(n)。您可以通过检查值来检查它的健全性:

A(1) = 1 iteration
A(2) = 2 + A(1) = 3
A(4) = 4 + A(2) = 7
A(8) = 8 + A(4) = 15
A(16) = 16 + A(8) = 31
A(32) = 32 + A(16) = 63
...

您会看到它呈线性缩放，其中 A(n) 基本上是 n 的线性因子。

回答评论:不，它不是 O(2n) 或 O(2n-1)。没有 O(2n)。都是 O(n)。参见 Plain english explanation of Big O .

编辑:您的示例有一个关键区别:它调用自己两次 而不是一次。再次检查结果。此外，这个版本有一个误导性的特征，即循环​​重复三次，但这里的三次是常量，如前所述，没有 O(n)，所以我只计算其中的 一个循环:

A(1) = 1
A(2) = 2 + 2 * A(1) = 4
A(4) = 4 + 2 * A(2) = 12
A(8) = 8 + 2 * A(4) = 32
A(16) = 16 + 2 * A(8) = 80
A(32) = 32 + 2 * A(16) = 192
...

那到底是什么关系呢？那么，如果您求解 A(n)(因为 n 是 2 的幂):

A(n) = n + 2 * A(n/2)
     = n + 2 * (n/2 + 2 * A(n/4))
     = 2n + 4 * A(n/4)
     = 2n + 4 * (n/4 + 2 * A(n/8))
     = 3n + 8 * A(n/8)

一般情况下你可以解决这个问题:

A(n) = log2(n) * n + A(n/n)
     = log2(n) * n + 1 (since A(1) = 1)

这就是 O(n log n) 的由来。