私は「コーディングをクラッキングする」という本を見ていたインタビュー "と質問に出くわした "スタックを昇順で並べ替えるプログラムを書いてください。アイテムを保持するために追加のスタックを使用するかもしれませんが、要素を他のデータ構造体（配列など）にコピーすることはできません。 、peek、isEmpty。 "
この本はO（n ^ 2）時間の複雑さとO（n）の空間で答えを出しました。
しかし、私は出会った このブログ クイックソート手法を用いてO（n log n）回の複雑さの解答を提供する。
私が思ったのは、空間の複雑さO（n ^ 2）ですね。このメソッドへの各呼び出しには、別の2つの再帰呼び出しとともに、別の2つのスタックを初期化する必要があるためです。
私はまだ空間の複雑さに少し揺れていますが、これはO（n ^ 2）スペースであるかどうかわかりませんが、各再帰呼び出しから生成された新しいスタックはレベルアップよりも小さくなります。
彼らの答えの背後に誰かが少し説明を与えることができれば、それは素晴らしいことだろう。
回答：
回答№1は1空間の複雑さは平均的にはO（n log n）である。空間の複雑さがO（n ^ 2）である場合、割り当てられた各空間が少なくとも1つのアクセスを必要とするので、時間の複雑さはどのようにO（n log n）になることができるか。
したがって、平均的な場合、スタックが各時間の半分に分割されると仮定すると、ith 再帰の深さ、配列のサイズはO（n / 2）になります^i）2で^私はi上の再帰ブランチth 深さ
したがって、iに割り当てられた合計サイズth 深さは O（n / 2 ^ i）* 2^i = 0（n）.
最大深度はlog nなので、全体の空間複雑さはO（n log n）です。
しかし、最悪の場合、空間の複雑さはO（n ^ 2）です。
回答№2の場合は1
クイックソートのこの方法では、空間の複雑さ時間の複雑さにちょうど追随します - 理由は非常に簡単です。各要素がサイズ1のスタックに入るまで、（ピボットを使用して）再帰的にサブスタックを分割しています。これはxサブスタック（log n深さ）の（2 ^ x = n）分割につながり、最終的にはそれぞれサイズ1のn個のスタックがあります。したがって、空間全体の複雑さはO（n * log n）になります。
この場合、スペース複雑さは、各反復で文字通り新しいスペースを占有するのとまったく同じです。したがって、最悪の場合、空間の複雑さはO（n ^ 2）になります。