0 
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"
4

4 回答 4

3

是的，它是 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)。请参阅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) 的来源。

于 2009-11-05T05:34:11.873 回答
1

是的。A[i] = A[i] + 1调用中的分配数量mystery(..., N)将是：

N + N/2 + N/4 + ... + 1

假设 N 是 2 的幂，则该系列的计算结果为2 * N - 1。将有等量的增量i，log2(N)'N>1' 的测试，对神秘和除法的递归调用。

粗略地说，这是4 * N + 3 * log2(N)操作（假设它们具有相同的权重……尽管没关系）。

对于某些常数 C1 和 C2，N趋于无穷大的极限在操作范围C1 * N内。C2 * N换句话说，计算复杂度是O(N)。

于 2009-11-05T05:46:04.970 回答
1

我现在正在对这个主题的期中考试进行评分！

无论如何，让我们将此算法的运行时间称为 T(n)。for 循环需要 n 时间，并且该函数使用值 n/2 调用自身。所以T(n)=T(n/2)+n。

我们可以使用Master Theorem解决这个递归问题，我们发现该算法采用 Theta(n)

于 2009-11-05T05:48:38.443 回答
0

是O(n)。

推导。您可以使用Master Theorem或更简单的扩展方式推导出它：

假设运行时间mystry()为T(n)，则为：

T(n) = n + T(n/2)   # n for the loop, T(n/2) for the recursive call
     = n + (1/2)n + T(n/4)
     = n + (1/2)n + (1/4)n + (1/8)n + ...
     = n (1 + 1/2 + 1/4 + 1/8 + ...)
     = n \Sum^{\inf}_{i=0} (1/2^i)
     = n * (2)
     = 2 n = O(n)
于 2009-11-05T05:56:58.630 回答