8

通常、マージソートは、シーケンスを半分に分割し、再帰的にソートすることによって実行されます。ただし、シーケンスを 3 分の 1 に分割してマージソートを実行することもできますか?

mergesort(array, start, last) {
tri_mid = (start+last)/3;
mergesort(array, start, tri_mid);
mergesort(array, tri_mid+1, last);
merge(array, start, last);
}

これは機能しますか？もしそうなら、bigO表記はどうなりますか？

4

4 に答える 4

3

はい、確かに機能しますが、マージソートの強みは、再帰的な分割統治アプローチです。リストを毎回半分に分割すると、O(log2(n)) が得られますが、計算の複雑さから、これは O(log n) と同等です。リストを等しくない 2 つの部分に分割すると、大きな O 式は O(log n) のままになります。これは、リストを各レベルでいくつかの部分に分割するためですが、リストを半分に分割するよりも遅くなる可能性があります。 、リストを分割し、各部分をソートし、ソートされたサブリストをマージする最適な状態でアルゴリズムが機能しないためです。. 考察の材料として、mergesort が最初の項目のみを左側のサブリストとして選択し、他のすべての項目を右側のサブリストとして選択した場合にどうなるか想像してみてください。次に、大きな O 式は O(n^2) になります。これは、他のより悪いアルゴリズムと同じくらい悪いものです。もちろん、自分の考えを試してみたい場合は、そうして時間を計ってください。そうすれば、何がより速いかを確実に知ることができます。

于 2013-04-27T19:08:36.173 に答える
1

ここに、そのようなマージソートの例があります:-)

void TRIPLE_MERGESORT(vector<double> &A, int k, int l)  
{
if(k<l)
    {
    int one_third = (l-k)/3;
    int two_third = 2*(l-k)/3;          // k < k+one_third < k+two_third < l
    TRIPLE_MERGESORT(A,k,k+one_third);
    TRIPLE_MERGESORT(A,k+one_third+1,k+two_third);
    TRIPLE_MERGESORT(A,k+two_third+1,l);
    MERGE(A,k,k+one_third,k+two_third);
    MERGE(A,k,k+two_third,l);
    }
}

MERGE は配列 (ベクトル) をマージします。これは、たとえば次のように実装できます。

void MERGE(vector<double> &A, int p, int q, int r)
{
int i = p;
int j = q+1;
int lenght = r - p + 1;
int k=0;
vector<double> merged;
merged.assign (lenght,0);
while((i<=q)&&(j<=r))
    {   
    if(A[i] <= A[j])
        {
        merged[k]=A[i];
        ++i;
        }
    else
        {
        merged[k]=A[j];
        ++j;
        }
    k++;
    }

if(j<=r)
    {
    while(j<=r)
        {
        merged[k]=A[j];
        ++j;
        ++k;
        }
    }
if(i<=q)
    {
    while(i<=q)
        {
        merged[k]=A[i];
        ++i;
        ++k;
        }
    }
for (i=0;i<lenght;++i)
    A[p+i]=merged[i];
}

良い１日を ：）

//編集：//

正確に言うことはできませんが (しかし、おそらく他の誰かがより適切に、そしてなぜこのようになっているのかを言うでしょう)、3 つの部分に分割することは、通常のマージソートよりも複雑 (およびより多くの作業が必要) であるため、より多くの時間がかかります。O（n ^ 2）になると思いますが、通常のマージソートよりも悪いのは確かです:)

于 2013-05-22T14:57:55.010 に答える
1

配列を 3 つの部分に分割すると、時間計算量の再帰方程式は :T(n)=3T(n/3)+O(n) になります。マスターの定理を使用すると、時間計算量は O(nlogn) になります。配列を同じ数の部分に分割しても、漸近的な複雑さは同じままです。この理由は、すべての再帰で 2 つのこと、つまり分割とマージを行う必要があるためです。マージには常に O(n) 時間がかかります。 . したがって、時間の複雑さを最小限に抑えることを考えている場合は、2 つの並べ替えられた配列を O(n) 時間未満でマージできるアルゴリズムを考えてみてください。

于 2014-10-27T02:13:06.760 に答える