たとえば、10個の文字列を入力した場合、これら2つの種類の最良または最悪のケースを取得するには、どのように入力できますか？
Heap sort: best case - nlogn worst case - nlogn Quick sort: best case - nlogn worst case - n^2 これら2つで混乱するのは、次のとおりです。
- ヒープ-最良の場合と最悪の場合は同じなので、入力順序は関係ありませんか？比較と割り当ての数は常に同じになりますか？ヒープソートでは、実際の作業は挿入で行われるので同じかもしれませんが、ソートでは最大/最小ヒープの削除のみが使用されますか？
- クイックソート-これはよくわかりません。私は ” mこれに対する最良の状況と最悪の状況が何であるかわからない。たとえば、すでにソートされている10個の文字列のリストの場合、再帰的アルゴリズムを完了するために常に同じ量のピボットを選択する必要はありませんか？この説明に関するヘルプは本当に役立ちます。
コメント
- クイックソートはランダム化アルゴリズムとして実装されることが多いことを理解する必要があります。これを知らないようです。
- $ n \ log n $と$ O（n \ log n）$の違いに注意する必要があります。ランダウ表記を参照してください。
回答
ヒープ-最良の場合と最悪の場合は同じであるため入力順序は関係ありませんか？比較と割り当ての数は常に同じになりますか？実際の作業は挿入で行われるため、ヒープソートでは同じかもしれませんが、ソートでは削除のみが使用されます。最大/最小ヒープ？それが理由ですか？
実際に行われる比較の数は、値が与えられる順序。最良の場合と最悪の場合がそれぞれΘ（n log n）であるという事実は、すべての要素が異なると仮定して、漸近的に違いがないことを意味するだけです。 2つの間では、一定の係数で異なる可能性があります。頭のてっぺんからこれの簡単な例はありませんが、比較の数が一定の係数で異なる入力を作成できると思います。 2つのアプローチ。ただし、big-O表記は定数を無視するため、これはベストケースとワーストケースの分析には反映されません。
クイックソート-これよくわかりません。これの最良の状況と最悪の状況が何であるかはわかりません。たとえば、すでにソートされた10個の文字列のリストの場合、再帰的アルゴリズムを完了するために常に同じ量のピボットを選択する必要はありませんか？この説明に関するヘルプは本当に役に立ちます。
選択されたピボットの数は、アルゴリズムの実行に関係なく実際に同じです。ただし、ピボットごとに行われる作業は、取得する分割の種類によって異なる場合があります。最良の場合、各ステップで選択されたピボットは、最終的に配列の中央値要素になります。これが発生すると、再帰の最上位レイヤーで（おおよそ）n回の比較が行われ、次に（おおよそ）n / 2のサイズのサブアレイが2つあるため、次のレイヤーでn回行われ、次のレイヤーで（おおよそ）nが行われます。サイズn / 4のサブアレイが4つあるため、レイヤー。Θ（log n）レイヤーがあり、各レイヤーはΘを実行するため。 （n）作業、実行された作業の合計はΘ（n log n）です。一方、ピボットとして各アレイの絶対最小値を選択することを検討してください。次に、（大まかに）n個の比較が最上層で行われ、次に（大まかに）次の層でn -1、次に（大まかに）次の層でn-2などが行われます。合計1 + 2 + 3 + … + nはΘ（n 2 ）であるため、最悪のケースです。
これがお役に立てば幸いです！
コメント
- 先生、ヒープソートnlognの最良のケースはどうですか？すべての要素が同一であると考えると、コストは配列のすべての要素を反復するだけで、ルートまでシフトアップすることはありません。ですから、私によれば、オメガ（n）である必要があります。
- それは良い点です。個別の要素を想定していたので、この回答を更新します。
回答
誰もいないのでまだ実際に対処されているheapSort：
配列として表される最大ヒープを使用し、その場で実行している場合は、最大要素を出力配列に逆方向に挿入するか、配列の背面に挿入すると仮定します。 、heapSortの最悪の場合の入力は、要素を削除するたびに「バブルダウン」または再ヒープ化を強制する入力です。これは、重複のないセットを並べ替えようとするたびに発生します。それでもΘ（n log n）、templatetypedefが言ったように。
このプロパティは、heapSortの最良のケースは、すべての要素が等しい場合であることを意味します（Θ（n）。削除するたびに再ヒープ化する必要がないため、log（n）時間かかります。ヒープの最大高さはlog（n））です。ただし、これは一種のひどい/非現実的なケースです。そのため、ヒープソートの実際の最良のケースはΘ（n log n）です。
コメント
- お粗末な非現実的なケースについてのあなたの意見は、私のアルゴリズムのクラスで尋ねられました。（トリックの質問に注意してください。）もちろん、私はまだあなたの意見に同意しています。（div id = “e407846b65″>
結果として私の答えが間違っていたXD）
回答
-
クイックソート
最悪の場合： $ \ mathcal {O}（n ^ 2）$ 。ピボット要素が常に右端の要素であると仮定しましょう：すでに入力します $ n $ 要素を含むソート済みリスト。したがって、各パーティション分割により、 $ n-1 $ 要素を含む1つのリストになります。 $ 0 $ 要素を含む1つのリスト。ピボット要素をランダムに選択した場合でも、それでも不運な場合があり、常にリストから最大値を選択します。
$ T（n）$ を比較のクイックソートの数とします。 $ n $ 要素でリストを並べ替える必要があります。最悪の場合： \ begin {align} T（n）= & T（n-1）+ n & \ text {（$ T（n-1）$ recursive、$ n $ to partion）} \\ = & \ frac {n（n + 1） } {2} \ in \ mathcal {O}（n）\ end {align}
ベストケース： $ \ mathcal {O}（n \ log n）$ 。ピボット要素がこのように選択されている場合は、リストが均等に分割されます。
\ begin {align} T（n）= & 2 \ T \ left（\ frac {n} {2} \ right）+ n &（\ text {2回$ \ frac {n} { 2} $再帰的、パーティションに$ n $）} \\ \ in & \ mathcal {O}（n \ log n）&（\ text {master theorem}）\ end {align}
-
ヒープソート
ヒープソートの最悪の場合と最良の場合の複雑さは、どちらも $ \ mathcal {O}（n \ log n）$です。 。したがって、ヒープソートでは、入力配列に対して $ \ mathcal {O}（n \ log n）$ の比較が必要です。ヒープソートの複雑さ：
\ begin {align} & \ mathcal {O}（n）&（\ text {build $（1、n）$ heap}）\\ + & \ sum_ {i = 1} ^ {n} \ mathcal {O}（\ log i- \ log 1）&（\ text {build $（1、j）$ heap}）\\ = & \ mathcal {O}（n）+ \ sum_ {i = 1} ^ {n} \ mathcal {O}（\ log i）&（\ text {logarithm quotient rule}）\\ = & \ mathcal {O}（n \ log n）& \ left（\ sum_ {i = 1} ^ {n} \ log i < \ sum_ {i = 1} ^ {n} \ log n = n \ log n \ right）\ end {align }
コメント
- あなたは' OP 'のすべての質問に回答したので、見逃した質問に回答します。ヒープソートは、'指定された数の要素に対して常に同じ数の比較を使用するとは限りません。最悪の場合は$ a \、n \ log n $で、最良の場合は$ b \、n \ log n $です。ここで、$ a > b $です。
- また、スリーウェイバリアントには単一要素入力の線形ベストケースがあることに注意してください。