反復特定のアルゴリズムとの関係

Question

おはよう。先週私のコースでは、実行時間を計算する方法と、与えられたアルゴリズムの漸化関係を決定する方法を学びました。私は繰り返しアルゴリズムには慣れていますが、再帰アルゴリズムには慣れていません。特に、2つの再帰的な呼び出しが1つずつ繰り返される場合。例えば

：

FindMin(int A[], int front, int last) 

if (last-front <= 1) 
    return A[front] 
else { 
    midpoint = (front+last)/2 
    int minFront = FindMin(A, front, midpoint) 
    minLast = FindMin(A, midpoint+1, last) 
    return min{minFront, minLast} 
} 

誰かが私には、この関数/それと類似した機能のための漸化式を決定するのに役立つ、との関係を決定するステップを通して私を導くことができれば、私は（あなたのブーツにキスします実際はそうではありませんが、あなたの助けは非常に高く評価されます）。あなたは二つの等しいサブタスクによってタスクを分割し、業務の一定の数を実行するため

Answer 1

あなたの再帰は、簡単な依存性によって説明されています。この再帰のための深さをスタック

T(n) = 2 * T(n/2) + C 
T(n) = 2 * (2 * T(n/4) + C) + C = 4 * T(n/4) + 3*C 
T(n) = 4 * (2 * T(n/8) + C) + 3*C = 8 * T(n/8) + 7*C 
... 
T(n) = n * T(1) + (n-1)*C = n * C = O(n) 

注ログ（N）であるので、スペースの複雑さ0（log（N））
（Abhishek Bansal追加のおかげで）