クイックソートは、O（log n）スタックスペースを必要とするという事実にもかかわらず、インサイチュ（インプレース）アルゴリズムとして説明されることがよくあります。つまり、insituは「必要な追加スペースがO（n）未満」を意味するのでしょうか、それともスタックスペースは一般にスペースの複雑さとしてカウントされないのでしょうか（しかし、なぜそうなるのでしょうか）、またはQuicksortは実際にはinsituアルゴリズムではありませんか？
4458 次
2 に答える
18
クイックソートは実際にはインサイチュアルゴリズムではありませんか？
それの標準的な実装はその場ではありません 。これはひどく一般的な誤解ですが、スタックスペースの消費のために正しく認識されているように、その概念は間違っています。
人々がアルゴリズムを変更してスペースアルゴリズムにしたので、私はそれの「標準的な実装」と言いO(1)ます。これが1つの例です：スタックのないクイックソート。
もちろん、古典的な時空のトレードオフと一致して、このようなバージョンのクイックソートは、標準の実装よりもパフォーマンスが低くなります。
于 2012-02-01T13:48:13.797 に答える
8
ウィキペディアは次の定義を提供しています：
コンピュータサイエンスでは、インプレースアルゴリズム（またはラテン語のinsitu）は、少量の一定量の追加ストレージスペースを持つデータ構造を使用して入力を変換するアルゴリズムです。
この定義によると、典型的なスタックベースのクイックソートは明らかにインサイチュアルゴリズムではありません。
実際、ウィキペディアの記事ではこれについて明示的に説明しています。
アルゴリズムは、入力を出力で上書きする限り、非公式にインプレースと呼ばれることがあります。実際には、これは（クイックソートの場合が示すように）十分ではなく、必要でもありません。たとえば、出力がストリームに対するものである場合、出力スペースは一定である場合もあれば、カウントされない場合もあります。
と
クイックソートは一般にインプレースアルゴリズムとして説明されていますが、実際にはそうではありません。ほとんどの実装では、分割統治法の再帰をサポートするためにO（log n）スペースが必要です。
ただし、@ Jasonが優れた回答で指摘しているように、O（1）の余分なスペースのみを必要とするクイックソートのバリアントが存在するようです。そのようなアロリスムは、その場で考慮されます。
于 2012-02-01T13:51:41.583 に答える