この Wikipidea の記事http://en.wikipedia.org/wiki/Quicksort#In-place_versionは、O(logn) がインプレース ソートの時空間複雑度であり、 http: //futur3googl3r.blogspot.com/2008/08/であることを示唆しています。 google-interview-questions.htmlこのインタビュー サイトは、O(n) であることを示唆しています。答えは O(n) だと思いますが、私が正しいかどうか知りたいです。
質問する
20310 次
2 に答える
13
両方の記事で言及されているスペースの複雑さは、余分なスペースのことです (元の配列を格納するために必要なスペースは数えません)。この余分なスペースは、余分な配列が宣言される一般的なケースに加えて、コール スタックから取得される場合があります。各再帰呼び出しは、スペースを占有する呼び出しスタックにスタック フレームを作成し、スタック フレームの数は入力サイズに依存するnため、カウントする必要があります。
@Jim Mischel が指摘したように、ブログはかなり一貫性がないため、ウィキペディアの記事を参照してみましょう。
インプレースクイックソートの場合、単純な実装から変更すると、単純な実装の余分なスペース（すべての場合）ではなく、平均してO(log n) 余分なスペースが得られます。ブログ1で正しく指摘されているように、余分なスペースの最悪のケースの複雑さは、アルゴリズムが最悪のケース (並べ替えられたリスト;再帰呼び出しがあるため、呼び出しスタックが余分なスペースを占有する) に遭遇したときです。O(n) O(n)nO(n)
1 : (指摘してくれた @rici に感謝) ただし、ウィキペディアの記事で言及されているように、最適化なしの実装を想定する場合にのみ、ブロガーは正しいです。最初に小さい部分を再帰し、長い部分の末尾呼び出しを実装することにより、最悪の場合にO(log n) 余分なスペースを使用するようにアルゴリズムを改善することができます。小さい部分は常に入力サイズの半分未満であるため、多くてもO(log n)再帰呼び出しが発生します。テールコールの最適化が行われていると仮定すると、長い部分は余分なスペースを発生させることなく現在のスタック フレームを再利用します。テールコールの最適化が行われていない場合は、明示的なスタックを使用して反復実装をいつでも作成できます。
于 2013-02-22T23:35:04.183 に答える
0
このインタビューは、それがO(n)であることを示唆しています
いいえ、そうではありません:
解決策: 最悪の場合でも、Quicksort は O(logn) のスペースの複雑さを持ちます。
于 2013-02-22T23:24:53.777 に答える