1

私は自分のアルゴリズムの教科書を読んでいて、漸化式について読んでいて、アルゴリズムが非常に複雑であることに気づいています。私はこの線に出くわします

"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がどこから来たのか説明できますか？

4

3 に答える 3

1

まあ、このステートメントは（おそらく）問題のアルゴリズムの議論、または少なくともステートメントの結論です。詳細がなければ、私は知識に基づいた推測しかできません。これは次のようになります。

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

唯一のわずかな奇妙な点は、発生する2つの定数係数が同じである理由が完全には明らかではないことです。しかし、big-O分析のポイントの一部は、定数係数が最終的には重要ではないということです。

于 2010-05-27T09:01:20.117 に答える
1

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

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

長さNの2つの配列をマージするためのO（N）アルゴリズムがあります。つまり、その複雑さは、定数b >0の場合はbNです。

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の場合（再帰を停止する基本的な場合）は簡単です。

于 2010-05-27T09:02:35.270 に答える
0 
T(n) = c if n < d
     = A*T(n/b) + f(n)

ここで、d> = 1であり、Aサブ問題があり、サブ問題は最大でn/bサイズです。f（n）は、問題をサブ問題に分割し、サブ問題のソリューションを問題全体のソリューションにマージするために必要な追加の合計時間です。

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

マージソートに2つのサブ問題があるのはなぜですか？

于 2010-05-27T09:12:32.200 に答える