アルゴリズムからの漸化関係の発見方法

Question

私は漸化関係を理解し​​ようとしています。私は、再帰によって整数の配列の最大要素を決定する方法を見つけました。以下はその機能です。最初に呼び出されるとき、nは配列のサイズです。

int ArrayMax(int array[], int n) { 
    if(n == 1) 
     return array[0]; 
    int result = ArrayMax(array, n-1); 
    if(array[n-1] > result) 
     return array[n-1]; 
    else 
     return result; 
} 

は、今私は漸化式とどのようにそこからビッグO記法に取得するを理解したいです。私はT（n）= aT（n/b）+ f（n）を知っていますが、aとbがどうなるべきかを知る方法はありません。

Answer 1

aは「何回の再帰呼び出しがあるか」で、bは「データを何個に分割するか」を直感的に示しています。再帰呼び出し内のパラメータは、nを何かで割ったものである必要はないことに注意してください。通常、nの任意の関数です。は、データの大きさがどのように変更されたかを表します。

たとえば、バイナリ検索では、各レイヤで1回の再帰呼び出しが行われ、データが2に分割され、各レイヤで一定の作業が行われるため、T(n) = T(n/2) + cになります。 Merge sortは、毎回2つのデータを分割します（分割は作業をnに比例させます）。の両方をサブアレイに再帰します。T(n) = 2T(n/2) + cnとなります。

あなたの例では、1回の再帰呼び出しを行い、毎回サイズを1ずつ減らして「データを分割する」ので、T(n) = T(n-1) + cになります。

これより大きなO表記を取得するには、置換または展開するだけです。あなたの例で、それは簡単です：

T(n) = T(n-1) + c = T(n-2) + 2c = T(n-3) + 3c = ... = T(0) + nc

あなたは、いくつかの「定数ベース」T(0) = c0を前提とした場合は、T(n) = nc + c0を取得し、行われる作業がO(n)であることを意味します。

バイナリ検索の例も似ていますが、置換を行う必要があります。n = 2^mを取得して、どこで取得できるかを確認してください。最後に、例の大きなO表記を導出する。 T(n) = T(sqrt(n)) + cは本当にクールなエクササイズです。

編集：再発関係を解決する他の方法があります - Master Theoremは標準的な方法です。しかし、その証明は特に良いことではありませんし、上記の方法は私が今まで適用したすべての再発に対して機能します。そして...まあ、それは数式に値を差し込むより面白いです。

T(n) = T(n-1) + constant 

とマスターの定理は言う：あなたのケースの漸化式で

Answer 2

がある

T(n) = aT(n/b) + f(n) where a >= 1 and b > 1 

ここでマスター定理があるため、マスターの定理 bのために適用することはできません1(b>1) より大きくなければなりませんあなたの場合にはb=1