0

これらの質問をグーグルとウィキで調べてみましたが、具体的な答えが見つからないようです。私が見つけたもののほとんどは、マスター定理での証明の使用に関連していましたが、より直感的に覚えられる平易な英語の何かを望んでいます. また、私は学校に通っていないため、これらの質問は面接用です。

メモリー：

メモリ使用量の観点からビッグオーを決定するとは、正確にはどういう意味ですか? たとえば、n 項目すべてを格納する必要がある場合に、ヒープソートが O(1) メモリで実行されると見なされるのはなぜですか? ヒープの構造を 1 つしか作成していないためですか? それとも、そのサイズがわかっているため、常に一定のメモリ使用量であるスタック上に作成できるためですか?

速度：

要素の追加が O(1) で行われ、パーコレーションが O(logn) で行われる場合、ヒープの作成はどのように O(n) 時間で行われますか? それは、O(1) で n 個の挿入を行わずに O(n) にし、各挿入後にパーコレートするのが O(logn) であることを意味するのではないでしょうか。したがって、合計で O(n) * O(logn) = O(nlogn) になります。また、ヒープソートのほとんどの実装では、パーコレートしてヒープを作成するのではなく、heapify 関数を使用していることにも気付きました。Heapify は O(nlogn) で n 回の比較を行い、O(1) で n 個の挿入を行うため、O(n) + O(nlogn) = O(nlogn) を取得しますか? 最初のアプローチは、n が小さい場合の 2 番目のアプローチよりも優れたパフォーマンスをもたらすでしょうか?

上記でこれを想定しましたが、O（1）操作をn回実行するとO（n）時間になるというのは本当ですか？それとも n * O(1) = O(1) ですか?

4

1 に答える 1

0

そこで、ウィキペディアからバイナリ ヒープの構築に関する有用な情報を見つけました: http://en.wikipedia.org/wiki/Binary_heap#Building_a_heap。

私の混乱の主な原因は、ヒープへの「挿入」が O(1) と O(logn) の両方であることにあったと思います. そのため、ヒープを作成した後は heapify を使用せず、代わりに O(logn) 挿入メソッドを使用します。

ヒープ プロパティを維持しながらアイテムを繰り返し追加する方法は、O(nlogn) で実行され、ヒープ プロパティを考慮せずにヒープを作成してからヒープ化する方法は、実際には O(n) で実行されます。これはあまり直感的ではなく、証拠なので、私はそれについて間違っていました。

注文されたアイテムを取得するための削除ステップは、各メソッドがヒープ プロパティを尊重するヒープを持っているため、同じコスト O(nlogn) です。

したがって、最終的には、ビルド ヒープ メソッドの O(1) + O(n) + O(nlogn) = O(nlogn) と O(nlogn) + O(nlogn) = O(nlogn ) 挿入方法。明らかに、特に小さな n の場合は、最初のほうが望ましいです。

于 2013-03-28T16:05:48.143 に答える