バイナリヒープで最小のイベントを見つけるのに O(log V) 時間がかかるのはなぜですか? (V は要素数)
クイックソート分割統治アルゴリズムは、最小要素を見つけるのに O(V) 時間かかります。バイナリ ヒープ内の最小要素を見つけることは、クイック ソートとほとんど同じですが (どちらも各ステップで問題のサイズを 2 で分割し、問題の数は同じままです)、なぜそれらの時間が異なるのでしょうか?
クイックソートを使用して最小の要素を見つけるのと、バイナリ ヒープ内の最小の要素を見つけるのにかかる時間が異なるのはなぜですか?
最小ヒープ (必ずしもバイナリではない) は、O(1)時間内に最小の要素を提供します。これは、最小の要素がヒープのルートである (ヒープ プロパティを満たす) ためです。
ここでの問題は、データ構造を混乱させていることだと思います。ソートされていないリストでは、どのアルゴリズムでも少なくともO(N)時間がかかります。ここで、N は要素の数です。
データがすでにヒープ構造に格納されている場合は、時間内に最小値を抽出できますO(1)。ただし、最初にソートされていないリストからヒープを構築するにはO(N)時間がかかることに注意してください。
ソートされたリストがある場合は、バイナリ検索を使用してO(log N)時間の最小値を見つけることができます。しかし、繰り返しますが、ソートには少なくともO(N).
クイックソートに非常によく似たピボットベースの選択アルゴリズムについて話していると仮定すると、どちらの場合も最小値を見つけることは根本的に異なります。つまり、クイックソートベースの選択アルゴリズムがピボットを選択して要素を分割すると、残りのセグメントのどれに番号が含まれているかがわかります。バイナリヒープには類似のプロパティがありません。ヒープの特別な特性は、すべてのノードがその親よりも小さいことです（最大ヒープについて話していると仮定します）。他の回答の1つと同様に、これにより、O（log（V））の実行可能な候補の数が制限されます。これは、バイナリヒープに含めることができるリーフの数です。ただし、（私が知る限り）葉のリストを維持する必要があります。または、これから時間計算量のメリットを得るには、ヒープを配列として表す必要があります。ヒープが最初の要素へのポインタを持つリンクされたノードのセットとして格納されている場合、最悪の場合、それが唯一の方法であるという理由だけで、すべての子を検索して最小値を見つける必要があります。葉。この質問にはすでに多くの答えがあり、それらのほとんどはほとんど正しいことを私は知っていますが、これがいくつかのことを明らかにすることを願っています。
また、明確にするために、実際のクイックソートソートアルゴリズム（ランダム化されている場合）は、償却されたO（nlogn）時間で実行されます。そして、ソートされた配列で最小の要素を見つけるのはO（1）です。
最大ヒープで最小の要素を見つけようとしていると仮定すると、あなたが言ったように、O(log V) 時間ではなく、O(V) 時間かかります。問題は各ステップで 2 つに分割されません。ルートよりも小さいことを確立すると、最小要素は 2 つのサブ トレスのいずれかにある可能性があるためです。したがって、min 要素を見つけるには、両方のサブツリーをトラバースする必要があります。