0

以下のアルゴリズムでは、マージソートの時間計算量は O(nlogn) であることがわかっています。

void mergesort(n elements) {
mergesort(left half);  ------------ (1)
mergesort(right half); ------------(2)
merge(left half, right half);

次の実装の時間計算量はどうなりますか?

(1)
void mergesort(n elements) {
    mergesort(first quarter);  ------------ (1)
    mergesort(remaining three quarters); ------------(2)
    merge(first quarter, remaining three quarters);

(2)
void mergesort(n elements) {
    mergesort(first quarter);  ------------ (1)
    mergesort(second quarter); ------------(2)
    mergesort(third quarter);  ------------ (3)
    mergesort(fourth quarter); ------------(4)
    merge(first quarter, second quarter,third quarter, fourth quarter);

複雑さを見つける方法を詳しく説明してください。

4

3 に答える 3

4

n の対数底 4 = log n / log 4 であるため、依然として O (n log n) であり、最終的には定数になります。

[編集]

k分割によるマージソートアルゴリズムの再帰関係は次のとおりです。k 個の並べ替えられた配列を合計 n 個の要素でマージすると、n log2(k) のコストがかかると仮定します。log2 は対数底 2 を表します。

T(1) = 0
T(n) = n log2(k) + k T(n/k)

繰り返し関係を次のように解決できます。

T(n) = n log2(n)

k の値に関係なく。

于 2013-10-14T10:04:19.000 に答える
3

これはあなたの質問に対する正確な答えではなく、ヒントであることに注意してください。

まず、デフォルトのマージソートの時間計算量がどのように n(log n) になるかを理解する必要があります。

8 つの要素があり、デフォルトのマージソート アプローチの場合、1 つの要素のみを含むグループに到達するまで毎回半分に分割すると、3 つの手順が必要になります。

したがって、N 個の要素に対して mergersort が 3 回呼び出されることを意味します。そのため、時間の複雑さは 3*8、つまり (log N)*N です。

ここに画像の説明を入力

デフォルトのパーティションを半分から他の比率に変更する場合は、1 要素のグループに到達するまでに何ステップかかるかを数える必要があります。

また、この回答は、複雑さの計算方法を説明することのみを目的としていることにも注意してください。すべてのパーティション アプローチの Big O の複雑さは同じであり、効率的な方法で実装されている場合、他の 2 つのパーティションでさえ、正確に N(logN) の複雑さになります。

于 2013-10-14T10:29:44.267 に答える
2

あなたが投稿した 3 つのアルゴリズムはすべて O(n log n) で、定数がわずかに異なります。

基本的な考え方は、log(n) パスを使用し、各パスで n 個の項目を調べるというものです。パーティションの大きさは問題ではなく、実際、さまざまなサイズのパーティションを持つことができます。常に O(n log n) になります。

ランタイムの違いはmergeメソッドにあります。並べ替えられたリストのマージは、O(n log k) 操作です。ここで、n はマージされるアイテムの総数、k はリストの数です。したがって、2 つのリストをマージn * log(2)することは であり、これはn(なぜならlog2(2) == 1) になります。

詳細については、MERGE SORT を使用して、ソートされた K 個の配列をソートする方法に対する私の回答を参照してください。

于 2013-10-14T14:41:13.867 に答える