Cel mai bun și mai rău caz de intrare pentru sortare heap și sortare rapidă?

heap- Deoarece cel mai bun și cel mai rău caz sunt aceleași nu contează ordinea de intrare? Numărul de comparații și atribuții vor fi întotdeauna aceleași? Îmi imaginez că într-un sortiment heap poate fi același, deoarece lucrarea reală se face la inserare, dar sortarea utilizează doar eliminarea heap max / min? De aceea?

Numărul comparațiilor făcute poate depinde de ordinea în care sunt date valorile. Faptul că cel mai bun și cel mai rău caz sunt fiecare Θ (n log n) – presupunând că toate elementele sunt distincte – înseamnă doar că asimptotic nu există nicio diferență între cele două, deși pot diferi cu un factor constant. Nu am exemple simple de acest lucru de pe capul meu, dar cred că puteți construi intrări în care numărul de comparații diferă de un factor constant între două abordări. Deoarece notația big-O ignoră constantele, totuși, acest lucru nu se reflectă în cea mai bună și cea mai proastă analiză.

sortare rapidă – Aceasta Nu stiu sigur. Nu sunt sigur care sunt cele mai bune situații și cele mai grave situații. Dacă este o listă deja sortată de 10 șiruri, de exemplu, nu ar trebui să alegem întotdeauna aceeași cantitate de pivoți pentru a obține complet algoritmul recursiv? Orice ajutor cu privire la această explicație ar ajuta cu adevărat.

Numărul de pivoti alesi este într-adevăr același, indiferent de execuția algoritmului. Cu toate acestea, munca efectuată per pivot poate varia în funcție de ce fel de diviziuni obțineți. În cel mai bun caz, pivotul ales la fiecare pas ajunge să fie elementul median al matricei. Când se întâmplă acest lucru, există (aproximativ) n comparații făcute la stratul superior al recursiunii, apoi (aproximativ) n la următorul strat, deoarece există două subarraiuri de dimensiunea n / 2, atunci există (aproximativ) n la următorul layer deoarece există patru subarrays de dimensiune n / 4 etc. Deoarece există Θ (log n) straturi și fiecare strat face Θ (n) lucru, lucrarea totală realizată este Θ (n log n). Pe de altă parte, luați în considerare alegerea minimului absolut al fiecărei matrice ca pivot. Apoi (aproximativ) n comparații se fac în stratul superior, apoi (aproximativ) n – 1 în următorul strat, apoi (aproximativ) n – 2 în următorul, etc. Suma 1 + 2 + 3 + … + n este Θ (n ² ), de unde cel mai rău caz.

Sper că acest lucru vă va ajuta!

Comentarii

• Domnule, cum este cel mai bun caz de heapsort nlogn? Dacă considerăm că toate elementele sunt identice, atunci costul ar fi doar iterarea prin toate elementele matricei și fără deplasare până la rădăcină. Deci ar trebui să fie omega (n) după mine.
• Acesta este un punct bun. Îmi asum elemente distincte, așa că voi actualiza acest răspuns.

Din moment ce nimeni nu s chiar s-a adresat heapSort încă:

Presupunând că folosiți o heap maximă reprezentată ca o matrice și introduceți elementele max înapoi în matricea de ieșire / în partea din spate a matricei, dacă o faceți în loc , cel mai rău caz de intrare pentru heapSort este orice intrare care vă obligă să „bulați în jos” sau să reheapificați de fiecare dată când eliminați un element. Acest lucru se întâmplă de fiecare dată când încercați să sortați un set fără duplicate. Va fi în continuare Θ (n jurnal n), după cum a spus templatetypedef.

Această proprietate implică faptul că cel mai bun caz al heapSort este atunci când toate elementele sunt egale (Θ (n), deoarece nu trebuie să reheapify după fiecare eliminare, care durează jurnal (n) de la înălțimea maximă a heap-ului este log (n)). Totuși, este „un caz urât / impracticabil, motiv pentru care cel mai bun caz real pentru heapsort este Θ (n log n).

Comentarii

• Punctul dvs. asupra cazului nepractic practic tocmai a fost pus în clasa mea de algoritmi. (feriți-vă de întrebări truc.) Desigur, eu ‘ sunt încă de acord cu punctul dvs. și am greșit răspunsul meu ca rezultat XD)

• Sortare rapidă

  Cel mai rău caz: $ \ mathcal {O} (n ^ 2) $ . Să presupunem că elementul pivot este întotdeauna cel mai drept element: Introduceți deja un listă sortată cu $ n $ elemente. Deci fiecare partiționare duce la o listă cu $ n-1 $ elemente și o listă cu $ 0 $ elemente. Chiar dacă alegeți elementul pivot în mod aleatoriu , puteți totuși să aveți ghinion și să alegeți întotdeauna valoarea maximă din listă.

  Fie $ T (n) $ numărul de comparații rapide necesită sortarea unei liste cu $ n $ elemente. Cel mai rău caz: \ begin {align} T (n) = & T (n-1) + n & \ text {($ T (n-1) $ recursiv, $ n $ la partiție)} \\ = & \ frac {n (n + 1) } {2} \ in \ mathcal {O} (n) \ end {align}

  Cel mai bun caz: $ \ mathcal {O} (n \ log n) $ . Dacă elementul pivot este ales în așa fel, acesta împarte lista în mod egal:

  \ begin {align} T (n) = & 2 \ T \ left (\ frac {n} {2} \ right) + n & (\ text {de 2 ori $ \ frac {n} { 2} $ recursiv, $ n $ la partiție)} \\ \ în & \ mathcal {O} (n \ log n) & (\ text {master teorema}) \ end {align}

• Sortare în grămadă

  Cel mai rău caz și complexitatea celor mai bune cazuri pentru sortarea heap sunt ambele $ \ mathcal {O} (n \ log n) $ . Prin urmare, sortarea heap are nevoie de comparații $ \ mathcal {O} (n \ log n) $ pentru orice matrice de intrare. Complexitatea sortării heap:

  \ 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 }

Comentarii

• Nu ai ‘ Am răspuns la toate întrebările despre OP ‘, așa că voi răspunde la una pe care ați ratat-o; sortarea heap nu ‘ nu folosește întotdeauna același număr de comparații pentru un număr dat de elemente. Cel mai rău caz este $ a \, n \ log n $, iar cel mai bun caz este $ b \, n \ log n $, unde $ a > b $.
• Rețineți, de asemenea, că varianta cu trei căi are liniar cel mai bun caz pentru intrarea unui singur element.