0

ヒープソートとマージソートを比較しながら、次のステートメントを読みました。

マージ ソートは、O(1) の余分なスペースを持つリンク リストで動作するように適合させることができます。ヒープ ソートは、O(1) の余分なスペース オーバーヘッドのみで二重リンク リストを操作するように適合させることができます。

これを説明する助けをいただければ幸いです (私はコンピューター サイエンスの教育を受けていません) — ただし、上記の並べ替えが初歩的なレベルでどのように機能するかは理解しています。

4

1 に答える 1

3

これはBig O Notationです。アルゴリズムの複雑さ (時間/メモリ使用量) を記述するために使用されます (詳細については、リンクを確認してください)。ここで意味するのは、あなたが読んだアルゴリズムは、前述のケースで機能するように拡張でき、必要な変更により、一定のスペースが必要になるということです。つまり、余分なスペースは構造のサイズに依存しません。それは一定です-たとえば、1つの変数がさらに多くなります。

編集：

最もよく使用される表記の一部:

  • O(1) - 定数 - 使用される時間またはメモリは、アルゴリズムが動作する構造のサイズに依存しません
  • O(n) - 線形 - 構造体のサイズに依存します - 構造体が大きいほど、より多くの時間/メモリが必要になります
  • O(logn) -対数 ...

詳しくはこちらをチェック

于 2013-07-26T08:32:44.730 に答える