0

この関数の算術演算に関する時間コスト (上限に関する) は?

int foo(int n)
{
    int i;
    if (n <= 3) return 1;
    else if (n > 333) 
    {
        i = n/2;
        return 3 * foo(i) + foo(i) + n * i; 
    }
    else return foo(n - 3) + 9; 
}

私はそれを分析しようとしました、そしてこれらは私の考えです：

  1. T(n) は次のとおりです。

       1 ; n ≤ 3 の場合
   4T(n/2) + (n 2 )/2 ; n > 333 の場合       
   T(n-3) + 9 ; それ以外は

  2. したがって、2 番目の式については、 と言えます。O((n2)/2 logn)

それが正しいか？

4

1 に答える 1

3

関数にスローされるすべての操作は一定時間の操作のみであることに惑わされないでください。加算、乗算、比較 - これらはすべて定数時間演算です。分岐再帰は、焦点を当てる必要があるものです。

複雑さをまったく変更せずに、関数を次の同等のものに再配置できます。

int foo(int n)
{
    if (n <= 3) return 1;
    else if (n <= 333) return foo(n - 3) + 9;
    else
    {
        int i = n/2;
        return 3 * foo(i) + foo(i) + n * i; 
    }
}

本質的な最初の 2 つのケースは、「nが一定の固定定数よりも小さい場合、一定量の作業が残っている」ことを示しています。したがって、最後のブロックを超えてしまう唯一の方法O(1)は、最後のelseブロックです。

そこでは、唯一の非一定時間操作は への 2 つの呼び出しfoo(n/2)です。したがって、再帰的な関係があります

T(n) = T(n/2) + T(n/2) = 2T(n/2)

利回り

T(n) = 2T(n/2) = 4T(n/4) = 8T(n/8) = ... = O(n)

したがって、 の複雑さはfoo(n)ですO(n)。

WolframAlpha は私に同意します:
http://www.wolframalpha.com/input/?i=T%28n%29+%3D+2*T%28n%2F2%29

T(n) = O(n) + 2*T(n/2)getという形の繰り返し関係が必要ですT(n) = O(n log n)。繰り返しますが、WolframAlpha は同意します:
http://www.wolframalpha.com/input/?i=T%28n%29+%3D+n+%2B+2*T%28n%2F2%29

于 2013-06-20T16:59:12.033 に答える