データ構造の漸化式

アルゴリズムの分析中に、いくつかの漸化式が見つかりました。これらの漸化式は、基本的に式で同じ関数を使用しています。再帰的アルゴリズム分析、および分割統治アルゴリズムのほとんどの場合、漸化式を取得します。

ここでは、いくつかの例を使用して、漸化式の1つの例を示します。二分探索手法を使用していると仮定します。この手法では、要素が最後に存在するかどうかを確認します。それが中央にある場合、アルゴリズムは終了します。そうでない場合は、実際の配列から左右のサブ配列を何度も取得します。したがって、各ステップで配列のサイズはn / 2ずつ減少します。バイナリ検索アルゴリズムの実行にT（n）の時間がかかるとします。基本条件にはO（1）の時間がかかります。したがって、漸化式は次のようになります-

$$ T（n）=\ begin {cases} T（1）＆for \：n \ leq 1 \\ T（| \ frac {n} {2} \ rvert）+ c＆for \：n> 1 \ end {cases} $$

同様に、マージソートのような別の例を選択した場合、その場合、リストを2つの部分に分割します。この分割は、リストサイズが1になるまで行われます。その後、並べ替えられた順序でそれらをマージします。マージアルゴリズムにはO（n）の時間がかかります。したがって、マージソートアルゴリズムにT（n）の時間がかかる場合、それを2つに分割し、それぞれに対して同じタスクを実行すると、T（n / 2）というようになります。したがって、漸化式は次のようになります-

$$ T（n）=\ begin {cases} T（1）＆for \：n =1 \\ 2T（\ frac {n} {2}）+ cn＆for \：n> 1 \ end {cases} $$

これらの方程式は、置換、漸化式などのさまざまな方法を使用して解くことができ、いくつかの特別な種類の漸化式は、マスター法を使用して解くことができます。