時間複雑度ヒープソートアルゴリズム

すべての場合において、ヒープソート時間の複雑さはnlog（n）です。時間複雑度ヒープソートアルゴリズム

しかし私は、なぜiil（i）の複雑さを持つiという子バイナリツリー上でheapifyアルゴリズムをn回呼び出す必要があるのか理解できません。

2017-11-18 Ronan Tarik Drevon

heapify操作には、O(lg(n))時間がかかります。最大/最小ノードをヒープの最下部から別のノードにスワップすると、そのノードを最後まで押し戻す必要があります。 n要素があり、ヒープの高さがlg(n)であるため、ノードがヒープを横切るときにlg(n)のスワップを行います。これを繰り返すとO(nlg(n))となります。

最悪の場合（入力はソートされていますが、逆の順序です）、ビルヒープとソートの両方がO(nlg(n))になります。最良の場合（ソートされた入力）の建物はO(n)になり、ソートはO(nlg(n))（入力が等しい値からなる場合はO(n)）になります。平均的な場合、建物は最善と最悪の間にあり、並べ替えはO(nlg(n))になります。

出典

2017-11-18 16:51:58 Whatever

バイナリツリーは、各親が最大2人の子供を持つように考えました。 –

@RonanTarikDrevon申し訳ありませんが、私はあなたの質問を誤解しました。私はあなたがバイナリサーチツリーを意味すると思った。バイナリツリーでは、各キーは最大で2つの子を持ち、それはバイナリツリーの唯一のプロパティです。 – Whatever

時間複雑度ヒープソートアルゴリズム

答えて

関連する問題