時間複雑漸化

Question

私は漸化式を見つける必要がある：

int search(int[] a, int l, int h, int goal) { 
    if (low == high) return 0; 
    int tg = target(a, l, h); 
    if (goal < target) 
     return search(a, l, tg-1, goal); 
    else if (goal > target) 
     return search(a, tg +1, h, goal); 
    else 
     return a[tg]; 
} 

この質問にアプローチするための初期の方法だろうか？私は解決策を求めているのではなく、それにアプローチするための最初の方法です。ありがとう！

Answer 1

正確な解決策を求めているわけではありません（しかし、私が望むならそれを提供することができます）。私はあなたにヒントを与えます。これは非常に単純ですが、そのような問題。

重要な考え方だが、この変更機能findTarget2呼ぶことにしましょう、おそらく最悪の複雑性を有するが、その期待複雑さを容易に測定することができる機能にあなたの機能を変更することです：今、f(n)せ

public static int findTarget2 (int[] a, int low, int high, int goal) { 
    if (low == high) return 0; 
    int len = high - low + 1; //length of the array range, i.e. input size 
    while (true) { 
     int target = selectTarget(a, low, high); 
     if (goal < target && target-low <= 3/4 * len) 
      return findTarget2(a, low, target-1, goal); 
     else if (goal > target && high-target <= 3/4 * len) 
      return findTarget2(a, target+1, high, goal); 
     else if (goal == target) 
      return a[target]; 
    } 

} 

を元の時間の複雑さであり、g(n)はfindTarget2関数の時間の複雑さです。ここで、nは入力のサイズ、つまりhigh-low+1に等しい配列の長さです。

さあ、言わせてその悪い実行でselectTarget結果であれば、それはしばらくの体内の任意の復帰コールが発生しない場合にのみ。

悪い実行のケースでは、findTarget2は基本的には同じ入力でそれ自身を呼び出すのに対し、元の関数は入力のサイズを少なくとも1減らすため、g(n) >= f(n)です。したがって、上限g(n)の場合、同じ制限がf(n)に適用されます。次のように期待値の線形性を利用して記述することができる

EX[g(n)] <= EX[g(3/4 * n) + X * O(n)] 

：

Xはランダム変数である

EX[g(n)] <= EX[g(3/4 * n)] + EX[X] * O(n) 

次のように次に、g(n)の予想される時間複雑さを記述することができます戻り値呼び出しまでのwhileループの実行回数を示し、最後のO(n)はfindTarget2関数で費やされた非再帰的な時間であり、それはですこれは、その時点でselectTarget関数が実行されているためです。

今、あなたの仕事はただEX[X]を計算し、その後、あなたはまた、f(n)の予想時間の複雑さの上限であるg(n)の最終予想時間の複雑さを、取得するためにMaster theoremを使用することができますので、の複雑さの上限元の関数。