アルゴリズムの漸化式を求める

Question

私はアルゴリズムの教科書を読んでいて、漸化式について読んでいて、アルゴリズムのビッグ O の複雑さを見つけています。私はこの線を越えて走ります

"In the case of the merge-sort algorithm, we get the recurrence equation:

    t(n) = b                  if n < 2

         = 2t(n/2) +bn        if n >= 2

for b > 0

私の反応は、「一体どうやってそれを知ったのですか？！？」でした。

したがって、アルゴリズムからこれらの漸化式を取得するための体系的なアプローチ、または単なる論理的な方法があるかどうか疑問に思っています。

b と 2 つの 2 がどこから来たのか誰か説明してもらえますか?

Answer 1

マージソートアルゴリズムは次のように要約できます。

mergesort (array A) {
   mergesort (first half of A);
   mergesort (second half of A);
   merge the two halves and return;
}

長さ N の 2 つの配列をマージする O(N) アルゴリズムがあります。その複雑さは bN 一定の b > 0.

の複雑さを仮定すると、 mergesort はT(N)です。N の半分は N/2 であるため、次のことがわかります。

mergesort (array A) {                    T(N)    =
   mergesort (first half of A);          T(N/2)  +
   mergesort (second half of A);         T(N/2)  +
   merge the two halves and return;       bN
}

これは N ≥ 2 の場合を説明します。

N < 2 のケース (再帰を停止する基本ケース) は自明です。

Answer 2

さて、この声明は (おそらく) 問題のアルゴリズムに関する議論の結論、または少なくとも声明です。詳細がなければ、次のように推測することしかできません。

• アルゴリズムが最初に行うことは、0 要素または 1 要素の処理を要求されているかどうかを確認することです。それが本当であれば、すぐに戻ります。したがって、それでは、 n < 2, 、固定費がかかります - それを呼び出してください b
• のために n >= 2, 、アルゴリズムは入力を 2 つの部分に分割し、それぞれのサイズを変更します。 n/2, 、各部分でそれ自体を呼び出します。このような呼び出しにはそれぞれ次のコストがかかります t(n/2), 、そのような呼び出しが 2 つあります
• 2 つの部分をマージして元に戻すには追加のコストがかかります。このコストは次の値に比例します。 n - あれを呼べ b 回 n

唯一のわずかな奇妙な点は、発生する 2 つの定数因子が同じである必要がある理由が完全には明らかではないことです。しかし、ビッグオー分析の要点の 1 つは、定数因子は最終的には重要ではなくなるということです。

Answer 3

T(n) = c if n < d
     = A*T(n/b) + f(n)

ここで、d>=1 で、A 個の副問題があり、副問題のサイズは最大でも n/b です。f(n) は、問題を部分問題に分割し、部分問題の解決策を問題全体の解決策にマージするために必要な追加時間の合計です。

これは分割統治アルゴリズム用です。

なぜマージソートには副問題が 2 つあるのでしょうか?