アルゴリズム空間の複雑さを計算する方法

Question

データ構造とアルゴリズム分析のレッスンを確認しています。 ソートをマージします と クイックソートアルゴリズム？

再帰の深さは、リンクされたリストマージソートのO（LGN）のみです

隣接するクイックソートに必要な追加のストレージスペースの量はO（n）です。

私の考え：

2つは両方とも分割と征服戦略を使用しているため、リンクリストマージのスペースの複雑さは、隣接するクイックソートと同じである必要があると思います。分割された半分。

ポインターをありがとう。

Answer 1

クイックソートの最悪のケースの再帰の深さは（必ずしも）O（ログN）ではありません。クイックソートは「半分」にデータを分割しないため、中央値のピボットの周りに分割されます。この[*]に対処するためにクイックソートを実装することは可能ですが、おそらくO（n）分析は、改善されたバージョンではなく、基本的な再帰的クイックソート実装のものでした。それは、あなたがブロッククォートで言うことと、あなたが「私の考え」の下で言うこととの間の矛盾を説明するでしょう。

それ以外はあなたの分析は健全だと思います - どちらのアルゴリズムも再帰レベルあたりの固定金額以外の余分なメモリを使用していないため、再帰の深さは答えを決定します。

矛盾を説明する別の可能な方法は、O（n）分析が間違っていることだと思います。または、「隣接するクイックソート」は私が以前に聞いた用語ではないので、それが私が思うことを意味しない場合（「配列のクイックソート」）、それは何らかの意味で必然的に宇宙が無効であるクイックソートを意味するかもしれません、その場で並べ替える代わりに割り当てられた配列を返すなど。しかし、QuickSortとMergesortをMergesortの再帰の深さとクイックソートの入力のコピーのサイズに基づいて比較するのはばかげているでしょう。

*]具体的には、両方の部分で関数を再帰的に呼び出す代わりに、ループに入れます。より小さな部分で再帰的な呼び出しを行い、より大きな部分を実行するためにループするか、後で行うための作業のスタックに大きな部分を押して（ポインター）、より小さな部分を実行するためにループします。いずれにせよ、作業の各塊があるので、スタックの深さがログNを超えないようにしてください いいえ スタックの上に置かれているのは、その前のチャンクの大部分の半分のサイズで、固定最小値まで（純粋にクイックソートで並べ替えている場合は1または2）。

Answer 2

私は「隣接するクイックソート」という用語にあまり精通していません。ただし、クイックソートには、実装方法に応じて、O（n）またはO（log n）スペースの複雑さのいずれかを持つことができます。

次のように実装されている場合：

quicksort(start,stop) {
    m=partition(start,stop);
    quicksort(start,m-1);
    quicksort(m+1,stop);
}

その後、空間の複雑さがあります の上）, 、一般的に信じられているようにO（log n）ではありません。これは、各レベルで2回スタックを2回押しているため、空間の複雑さは再発から決定されます。

T(n) = 2*T(n/2)

パーティションがアレイを2つの等しい部分に分割すると仮定します（ベストケース）。これによるとこれの解決策 マスター定理 t（n）= o（n）です。

上記のコードスニペットで2回目のクイックソートコールをテールリクールに置き換えると、t（n）= t（n/2）、したがってt（n）= o（log n）を取得します（マスター定理のケース2で）。

おそらく、「連続したクイックソート」は、2つのクイックソート呼び出しが互いに隣にあるため、最初の実装を指します。その場合、スペースの複雑さは の上）.