データ構造における置換方法

ここでは、置換法を使用して漸化式を解く方法を説明します。それをよりよく理解するために、2つの例を取り上げます。

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

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

解く-結果を得るために、各ステップで数式を代入します-

$$ T（n）=T（\ frac {n} {2}）+ c $$

T（N / 2）に置き換えることで、次のように書くことができます。

$$ T（n）=（T（\ frac {n} {4}）+ c）+ c $$

$$ T（n）=T（\ frac {n} {4}）+ 2c $$

$$ T（n）=T（\ frac {n} {8}）+ 3c $$

$$ T（n）=T（\ frac {n} {2 ^ {k}}）+ kc $$

ここで、$$（\ frac {n} {2 ^ {k}}）$$が1に達すると、2 ^k であることを示します。 nです。したがって、kの値はlo​​g ₂です。 𝑛

T（n）=ϴ（log n）

同様に、マージソートのような別の例を選択した場合、その場合、リストを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} $$

解く-結果を得るために、各ステップで数式を代入します-

$$ T（n）=2T（\ frac {n} {2}）+ cn $$

T（N / 2）に置き換えることで、次のように書くことができます。

$$ T（n）=2（2T（\ frac {n} {4}）+ \ frac {cn} {2}）+ cn $$

$$ T（n）=4T（\ frac {n} {4}）+ 2cn $$

$$ T（n）=8T（\ frac {n} {8}）+ 3cn $$

$$ T（n）=2 ^ {k} T（\ frac {n} {2 ^ {k}}）+ kcn $$

ここで、$$（\ frac {n} {2 ^ {k}}）$$が1に達すると、2 ^k であることを示します。 nです。したがって、kの値はlo​​g ₂です。 𝑛。そして、T（n）は-