0

与えられたシーケンスが約 3 分の 1 の等しいサイズの 3 つのサブシーケンスに分割される、修正マージ ソート アルゴリズムを説明してください。アルゴリズムの時間計算量を漸近的に分析します。これを解決するには？

4

1 に答える 1

1

これはおそらくあなたの宿題ですが、Cormen、Lierson、Rivestの第2章を読むことをお勧めします。

この漸化式を解く-T（n）= 3T（n / 3）+ O（n）

すべての問題は3つのサブ問題に細分され、元のデータのn/3の部分が含まれています。それにマスター定理を適用すると、答えは0（n * log（n））であることがわかります。

Note - here logarithm is of base 3 .
于 2012-12-26T13:59:49.607 に答える