さまざまなソートアルゴリズムの空間複雑さを理解しようとしています。私としてクイックソートはO バブルソート、挿入及び選択ソートの複雑さはOであることを（1）
（）N（ログ）が見つかりました。上記のリンクから異なるソートアルゴリズムの空間複雑度の差
http://bigocheatsheet.com/?goback=.gde_98713_member_241501229
とマージソートは、（Oでありますn）。
私たちは実際にアルゴリズムのいずれかで余分なメモリを割り当てていませんでした。 次に、同じ配列を使用して並べ替えるときに、空間の複雑さが異なるのはなぜですか？
あなたがコードを実行すると、メモリは二つの方法で割り当てられます
暗黙のうちに、あなたが関数呼び出しを設定すると。
明示的に、あなたはメモリのチャンクを作成します。
クイックソートは、暗黙のメモリ使用の例です。私がクイックソートをやっている間、私は回帰的に最悪の場合にはO(n)回、平均的にはO(log(n))と呼んでいます。それらの再帰呼び出しのそれぞれは、O(n)の最悪のケースと平均の場合はO(log(n))になるために、追跡するためにそれぞれO(1)スペースを取る。
Mergesortは、明示的にメモリを使用する良い例です。私はソートされたデータの2つのブロックを取って、マージを配置する場所を作成し、それらの2つからそのマージにマージします。マージ先の作成はO(n)データです。
O(1)メモリに割り当てるには、メモリを割り当てず、再帰的に自分自身を呼び出さないようにする必要があります。これは、バブル、挿入、および選択ソートのすべてに当てはまります。
ソートしている配列が参照渡しされていると仮定します。配列のスペースは、空間の複雑さの分析に含まれないと仮定しています。
クイックソートのスペースの複雑さは、賢明な実装でO(n)（無作為化クイックソートの場合はO(log n)と予想されます）とすることができます。サブ配列全体をコピーするのではなく、単にインデックスを渡すだけです。
クイックソートのためO(n)は、「ネストされた」再帰呼び出しの数はO(n)ことができるという事実から来ている：あなたはピボットのための不運な選択肢を作り続けるとどうなるかを考えます。各スタックフレームにはO(1)のスペースが必要ですが、O(n)のスタックフレームがあります。ランダムなクイックソートについて話している場合、と予想されるの深さ（つまり予想されるスタックスペース）はO(log n)です。
マージソートの場合、最大でO(log n)の "ネスト"再帰呼び出しを行うため、スペースの複雑さはO(log n)になると思います。
さらに、マージソートの時間的な複雑さは、スタック領域の場合はO(log n)に、配列の場合はO(n)になります。つまり、合計の領域の複雑さはO(n)です。クイックソートの場合はO(n)+O(n)=O(n)です。
これらのアルゴリズムのそれぞれを実装するには、さまざまな方法があり、実装ごとに空間の複雑さが異なることに注意してください。
マージソートから始めましょう。配列上のmergesortの最も一般的な実装は、個々の範囲のマージを実行する外部バッファを割り当てることによって機能します。これには、配列のすべての要素を保持するためのスペースが必要です。余分なスペースを必要としますΘ（n）。しかし、代わりに、各マージに対してインプレースマージを使用することができます。つまり、必要な余分なスペースは、再帰呼び出しのスタックフレームのスペースとなり、スペースの複雑さはΘ（log n）になります。アルゴリズムの実行時間を大きな一定の係数で増加させます。代わりに、O（1）余分なスペースしか必要としませんが、より高い定数を持つインプレースマージを使用して、ボトムアップのマージソートを実行できます。
一方、リンクされたリストをマージする場合、スペースの複雑さはかなり異なることになります。要素自体が簡単に再配線できるので、リンクされたリストを空間O（1）にマージできます。これは、再帰呼び出しのスタックフレームを格納するために必要な領域から、マージソートリンクリストの領域の複雑さがΘ（log n）であることを意味します。
別の例としてクイックソートを見てみましょう。 Quicksortは通常外部メモリを割り当てませんが、使用するスタックフレームにはスペースが必要です。ピボットが常に配列の最大要素または最小要素になる場合、クイックソートの素朴な実装では、スタックフレームの最悪の場合にはスペースΘ（n）が必要になることがあります。この場合、サイズnの配列 - 1、n - 2、n - 3などがあります。ただし、基本的にテールコール除去という標準的な最適化があります。つまり、配列の2つの半分の小さい方の部分で再帰的にquicksortを呼び出し、より大きな半分の現在の呼び出し。つまり、サイズが最大n/2、次にn/4、n/8などのサブアレイで再帰呼び出しに新しいメモリを割り当てるだけなので、領域使用量はO（log n）に減少します。