2

トップダウン マージ ソートでは、再帰関数は次のように呼び出されます。

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

この戦略の空間複雑度は O(n) であると教科書に記載されています。一方、再帰をよく見ると、再帰呼び出しで配列へのポインターを渡しています。2 番目に、最下位ノードを親ノードにマージすることにより、トラバーサルの前の順序で再帰が解決されます。そのため、毎回スタック上に O(logn) 個の変数 (またはスタック上に O(log n) 個のフレーム) があります。では、インプレース マージ技術があるにも関わらず、空間の複雑さが O(n) であるのはどうしてでしょうか?

4

4 に答える 4

4

では、インプレース マージ技術があるにも関わらず、空間の複雑さが O(n) であるのはどうしてでしょうか?

あなたの本に記載されている実装では、おそらくインプレース マージ手法を使用していないためです。O(1) スペースと O(n log n) 時間の並べ替えが必要な場合は、マージ並べ替えよりもヒープ並べ替えの方がはるかに簡単なため、通常はヒープ並べ替えが優先されます。リストの並べ替えについて話している場合にのみ、O(1) マージ並べ替えを実行する意味があります...そして、それは簡単です。たとえば、リンクされたリストに指定されたマージソートは、O(1) スペースと O(n log n) 時間になります。

ここでの根本的な誤解は次のように思われます: 時間の複雑さは、アルゴリズムが解決する問題ではなく、アルゴリズムに適用されます。必要に応じて O(n^3) マージソートを記述できます...私のアルゴリズムが O(n^3) ではないという意味ではなく、O(n log n) マージについては何も言いません選別。これは、計算の複雑さとは少し異なります。たとえば、P にある問題について話します... 多項式時間アルゴリズムがある場合、問題は P にあります。ただし、P の問題は非多項式時間アルゴリズムでも解決できます。考えてみれば、そのようなアルゴリズムを構築するのは簡単なことです。空間の複雑さについても同じことが言えます。

于 2011-08-03T20:31:02.670 に答える
2

再帰呼び出しによって占有されるスペースが O(log n) であることは正しいです。

しかし、配列自体が占めるスペースは O(n) です。

総スペースの複雑さは O(n) + O(log n) です。

これは、(n)=>2(n) によって上に制限されているため、O(n) です。

于 2011-08-03T18:53:05.503 に答える
1

どうやって宇宙nにアイテムを保管するつもりですか？log nそれは意味がありません。nアイテムを並べ替える場合は、O(n)スペースが最適です。

于 2011-08-03T18:50:19.153 に答える
0

定数以外のマージソート関数内にスペースを割り当てていないため、このスペースの複雑さは O(lg(n)) です。ただし、配列の場合、マージ手順はメモリを割り当てるため、O(lg(n)) + O(n) = O(n) になることに注意してください。リンクされたリストを使用すると、マージ手順内のスクラッチスペースを回避できるため、O(lg(n) 最適) に到達します。

于 2012-04-19T00:52:15.087 に答える