分割と征服の解決策として番号を付ける

理論計算科学では分割と征服のアルゴリズムとして数字を付けると、ランタイムはT(n) = 2T(n/2) + Θ(1)となりますが、先生のスライドによればそれはT(n) = T(n/2) + Θ(1)です。どうして？私はアルゴリズムが2つのサブ問題に分割されるので、2を追加しましたか？私が間違っている？分割と征服の解決策として番号を付ける

出典

2017-08-23 ToTom

答えに乗数（2）があるのはなぜですか？説明できますか？ –

はい、私が理解する限り、数字（私の場合は2）は、a = n/2 * a^n/2の問題として、2つの副問題のような部分問題の数です。一方、n/2は部分問題のサイズを表す。 – ToTom

2つの部分の答えが同じではありませんか？ではなぜそれを2回呼び出す必要がありますか？ –

各ステップで、問題は2つの小さな同一の部分に分割されます。これらは同一であるため、それぞれの計算を行う必要はありません。したがって、乗算器2は必要ありません。

出典

2017-08-23 14:16:55

ああ、ありがとう！とった。 – ToTom

分割と征服の解決策として番号を付ける

答えて

関連する問題