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、

トロント大学