-1

次のコードは、パラメーターサイズに関してどのくらいの時間計算量がありますか？動機付ける。

// Process(A, N) is O(sqrt(N)). 

Function Complex(array[], size){
    if(size == 1) return 1;
    if(rand() / float(RAND_MAX) < 0.1){
        return Process(array, size*size)
             + Complex(array, size/2)
             + Process(array, size*size);
    }
}

Process（A、N）がO（sqrt（N））の場合、Process（A、N * N）はO（N）であり、Complex（array、size / 2）である必要があるため、O（N）だと思います。 ）はO（log（n））です。これは、実行するたびにサイズが半分になるためです。したがって、1回の実行で、O（N）+ O（log（N））+ O（N）= O（N）が必要になります。

私を訂正して、私がこのような課題をどのように考え/進めるべきかについてのヒントを教えてください。

よろしくお願いします。

4

1 に答える 1

0

アルゴリズムの時間計算量はO(N)確かですが、別の理由があります。

関数の複雑さは次のように表すことができますT(n)。

T(n) = T(n/2)       +       2*n
        ^                   ^
      recursive          2 calls to 
      invokation        Process(arr,n*n),
                          each is O(n(

この再帰はO（n）であることがよく知られています。

T(n) = T(n/2) + 2*n = 
     = T(n/4) + 2*n/2 + 2*n = 
     = T(n/8) + 2*n/4 + 2*n/2 + 2*n
     = ....
     = 2*n / (2^logN) + ... + 2*n/2 + 2*n
     < 4n
     in O(n)

それを正式に証明しましょう。数学的帰納法を使用します。

ベース： T（1）<4（チェック）
仮説：、、およびnすべてk<nの主張T(k) < 4k が当てはまります。
の場合n：

T(n) = T(n/2) + n*2 = (*) 
     < 2*n + 2*n 
     = 4n

結論：T(n)_O(n)

（*）帰納仮説から

于 2013-01-13T15:38:38.083 に答える