0

私はそれをプログラムする方法についてはかなり明確ですが、定義についてはよくわかりません。たとえば、数学用語で書き留める方法などです。通常のヒープソートは、O 表記の N 要素で実行されます。O(log(n)) ヒープソートを始めたばかりなので、ここで少しずれている可能性があります。しかし、N 個の要素がある場合、たとえばランダムな要素を探すにはどうすればよいでしょうか。そして、そのランダムな要素を選んで削除しますか? 最悪の場合、ツリー全体を通過する必要があると考えていました(要素が最初の場所または最後の場所、たとえば最高または最低のいずれかにある可能性があるため)。しかし、どうやってそれを数学用語で書き留めることができますか?

4

2 に答える 2

0

Heapsortの最悪の場合のパフォーマンスは O(n log n) であり、alestanisを引用すると:

最大ヒープの最大値: O(1)。最小ヒープ内の最小値: O(1)。O(n) の反対のケース。

これは、ヒープを自分で作成する場合に O(1) で反対のケースを行う方法を説明する SO-answer です

于 2012-10-28T22:31:22.627 に答える