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）時間で実行されます（回答による）。なんでそうなの？これら2つは、いくつかの定数だけ異なるはずですが。

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

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 に答える