algorithm - 計算時間 - マージソート時間と空間複雑度




マージソート 英語 (4)

MergeSort time Complexityは基本的な知識であるO(nlgn)です。 マージソート空間の複雑さは常に配列を含むO(n)です。 スペースツリーを描画すると、空間の複雑さはO(nlgn)のように見えます。 ただし、コードは深さ優先コードなので、常にツリーの1つのブランチに沿ってのみ展開されるため、必要な領域の合計使用量は常にO(3n)= O(n)で囲まれます。

たとえば、スペースツリーを描画すると、O(nlgn)のように見えますが、

                             16                                 | 16
                            /  \                              
                           /    \
                          /      \
                         /        \
                        8          8                            | 16
                       / \        / \
                      /   \      /   \
                     4     4    4     4                         | 16
                    / \   / \  / \   / \
                   2   2 2   2.....................             | 16
                  / \  /\ ........................
                 1  1  1 1 1 1 1 1 1 1 1 1 1 1 1 1              | 16

ツリーの高さはO(logn)=>空間の複雑さはO(nlogn + n)= O(nlogn)です。 ただし、実際のコードでは並列実行されないため、このようなことはありません。 たとえば、N = 16の場合、これがmergesortのコードの実行方法です。 N = 16。

                           16
                          /
                         8
                        /
                       4
                     /
                    2
                   / \
                  1   1

使用されるスペースの数が32 = 2n = 2 * 16 <3nであることに注意してください

その後、それは上向きにマージされます

                           16
                          /
                         8
                        /
                       4
                     /  \
                    2    2
                        / \                
                       1   1

34 <3nである。 その後、それは上向きにマージされます

                           16
                          /
                         8
                        / \
                       4   4
                          /
                         2
                        / \ 
                       1   1

36 <16×3 = 48

それが上に合流する

                           16
                          / \
                         8  8
                           / \
                          4   4
                             / \
                            2   2
                                /\
                               1  1

16 + 16 + 14 = 46 <3 * n = 48

より大きい場合、n = 64

                     64
                    /  \
                   32  32
                       / \
                      16  16
                          / \
                         8  8
                           / \
                          4   4
                             / \
                            2   2
                                /\
                               1  1

64 * 3 = 3 * n = 3 * 64

これは、一般的なケースの誘導によって証明できます。

したがって、並列で並列に実行するのではなく、マージ後に使用済み領域をクリーンアップしている限り、配列を実装する場合でも、空間の複雑さは常にO(3n)= O(n)で囲まれます。

私の実装の例を以下に示します:

templace<class X> 
void mergesort(X a[], int n) // X is a type using templates
{
    if (n==1)
    {
        return;
    }
    int q, p;
    q = n/2;
    p = n/2;
    //if(n % 2 == 1) p++; // increment by 1
    if(n & 0x1) p++; // increment by 1
        // note: doing and operator is much faster in hardware than calculating the mod (%)
    X b[q];

    int i = 0;
    for (i = 0; i < q; i++)
    {
        b[i] = a[i];
    }
    mergesort(b, i);
    // do mergesort here to save space
    // http://stackoverflow.com/questions/10342890/merge-sort-time-and-space-complexity/28641693#28641693
    // After returning from previous mergesort only do you create the next array.
    X c[p];
    int k = 0;
    for (int j = q; j < n; j++)
    {
        c[k] = a[j];
        k++;
    }
    mergesort(c, k);
    int r, s, t;
    t = 0; r = 0; s = 0;
    while( (r!= q) && (s != p))
    {
        if (b[r] <= c[s])
        {
            a[t] = b[r];
            r++;
        }
        else
        {
            a[t] = c[s];
            s++;
        }
        t++;
    }
    if (r==q)
    {
        while(s!=p)
        {
            a[t] = c[s];
            s++;
            t++;
        }
    }
    else
    {
        while(r != q)
        {
            a[t] = b[r];
            r++;
            t++;
        }
    }
    return;
}

これが役立つことを願っています!=)

すぐにChee Loong、

トロント大学

Merge Sortの実装を例にしてみましょう

void mergesort(Item a[], int l, int r) {
if (r <= l) return;
int m = (r+l)/2;
mergesort(a, l, m);  ------------ (1)
mergesort(a, m+1, r); ------------(2)
merge(a, l, m, r);

a)このマージソートの時間複雑さはO(nlg(n))です。 パラレル化(1)と(2)は実用的な利益をもたらすだろうか? 理論的には、それらを並列化した後でも、O(nlg(n))で終わるように見えますが、実質的に何らかの利益を得ることができますか?

b)このマージソートの空間複雑度はここではO(n)です。 しかし、リンクリストを使用してインプレースマージソートを実行することを選択した場合(配列を合理的に行うことができるかどうかはわかりません)、再帰スタックフレームサイズを考慮する必要があるため、空間の複雑さはO(lg ? O(lg(n))を定数64として扱うことができますか? 私は数箇所の場所でこれを誤解しているかもしれません。 64の意義は何ですか?

c) http://www.cprogramming.com/tutorial/computersciencetheory/sortcomp.htmlよれば、マージソートではリンクリストを使って一定のスペースが必要です。 どうやって ? 彼らはO(lg(n)constant)を扱いましたか?

d)[もっと分かりやすくするために]空間の複雑さを計算するために、入力配列またはリストが既にメモリにあると仮定するのは公正でしょうか? 私が複雑さの計算をするとき、私はいつも入力によって既に取られたスペースのほかに必要となる "余分な"スペースを計算します。 それ以外の場合は、空間の複雑さは常にO(n)またはそれより悪くなります。


a)はい、完璧な世界では、サイズn、n / 2、n / 4のlog nマージをしなければならないでしょう(あるいは、1,2,3 ... n / 4、n / 2 、n - 並列化できません)、O(n)を与えます。 それはまだO(n log n)です。 それほど完璧ではない世界では、無限の数のプロセッサーがなく、コンテキスト切り替えや同期化によって潜在的な利益が相殺されます。

b)空間の複雑さは、要素をどこかに格納する必要があるので、常にΩ(n)です。 追加の空間の複雑さは、配列を使用する実装ではO(n)、リンクリストの実装ではO(1)になります。 実際には、リストを使用する実装では、リストポインタのために追加のスペースが必要です。すでにリストをメモリに入れていない限り、それは問題ではありません。

O(n)+ O(log n)なので、配列の場合はまだO(n)です。 リストの場合、それはO(ログn)の追加メモリです。

c)リストは、マージ処理中に変更されたポインタを必要とするだけです。 それには一定の追加メモリが必要です。

d)そのため、マージソートの複雑さ分析では、人々は「スペースの追加要件」やそれに類するものについて言及しています。 要素をどこかに保存しなければならないことは明らかですが、純粋主義者を守るためには、「追加のメモリ」について言及するほうが常に優れています。


スペースの複雑さ:各レベルでサブアレイ/サブリストが作成された場合のそのnlogn(各レベルで必要なログレベル* nスペース=> logn * n)。 そうでなければ、スタック空間を考慮すると、LinkedListではlogn、Arrayではn(n + logn = n)となります。 時間の複雑さ:最悪および平均の場合のnlogn


マージソートの最悪ケースパフォーマンス: O(n log n) 、マージソートのベストケースパフォーマンス: O(n log n)typicaly、O( n) 、マージソートの最悪ケースの空間複雑性: О(n)total、O(n)auxiliary





space-complexity