バイナリツリー検索の複雑さ

バイナリヒープの検索に関する競合する情報が見つかりました。それによるとhttps://en.wikipedia.org/wiki/Binary_heap、これはO（n）（編集：実際にはO（ログn））です。これによれば、Search an element in a heapはO（n/2）です。バイナリツリー検索の複雑さ

出典

2016-05-23 tobias_theblowhard

私は申し訳ありませんが、私はウィキペディアのリンクはそれがO（ログn）だと言いました。 –

真のバイナリヒープは、Wikipediaで*ヒーププロパティ*が記述されているため、O（n/2）になります。* AがBの親ノードである場合、ノードAのキーはノードBのキーに関して同じ順序がヒープ全体に適用されます。*順序は本質的に検索の努力を半分に分割します。しかし、その複雑さはグラフ上で線形であるため、本質的にO（n）に平均化されます。バイナリ検索ツリーは子供を注文し、O（log n）の複雑さを有する真のバイナリ検索を行うことを可能にする。 –

「検索」が特定のデータをヒープで検索することを意味する場合は、「O（n）」にする必要があります。私はwikiページが実際に何を意味するのか分かりません。しかし、通常、ヒープは "検索"操作をサポートしていません - それらはそれを行うように設計されていません。たぶん、誰かがwikiページを修正するか、より明確に述べるべきです。 – WhatsUp

ウィキペディアは間違っていました。バイナリヒープは、個々の要素を検索するようには設計されておらず、最小の要素にアクセスできるように最適化されています。これは、例えば、時間内に構築できるようにするものです。Θ（n）;彼らが要求する順序は、バイナリ検索ツリーほど厳密ではありません。

誰かがウィキペディアを更新しているようです。いいですね。それを指摘してくれてありがとう！

1つの注記 - 技術的には正しいO（n/2）という用語は、big-O表記法の貧弱な使用とみなされます。 Big-O表記は定数を無視するので、O（n/2）はO（n）と同じです。特定のオペレーション数を数えたい場合は、big-O表記を避け、「正確にn/2の比較が必要です」と言ってください。

出典

2016-05-25 00:26:27 templatetypedef

バイナリツリー検索の複雑さ

答えて

関連する問題