Beste og verste tilfeller for haugsortering og rask sortering?

heap- Siden det beste og verste tilfellet er det samme spiller det ingen rolle inngangsrekkefølgen? Antall sammenligninger og oppgaver vil alltid være det samme? Jeg forestiller meg at i en haugsortering kan det være det samme siden det virkelige arbeidet er gjort i innsettingen, men sorteringen bruker bare fjerning av maks / min haug? Er det derfor?

Antall sammenligninger som faktisk er gjort kan avhenge av rekkefølgen som verdiene er gitt i. Det faktum at det beste og verste tilfellet er Θ (n log n) – forutsatt at alle elementer er forskjellige – betyr bare at asymptotisk det ikke er noen forskjell mellom de to, selv om de kan variere med en konstant faktor. Jeg har ikke noen enkle eksempler på dette fra toppen av hodet mitt, men jeg tror at du kan konstruere innganger der antall sammenligninger avviker med en konstant faktor mellom to tilnærminger. Siden stor-O-notasjon ignorerer konstanter, gjenspeiles ikke dette i best-case og worst-case analyse.

quick sort- This one Jeg vet ikke helt sikkert. Jeg er ikke sikker på hva de beste tilfellene og worst case-situasjonene er for dette. Hvis det for eksempel er en allerede sortert liste med 10 strenger, trenger vi ikke alltid velge samme mengde pivoter for å fullføre den rekursive algoritmen? Enhver hjelp til denne forklaringen vil virkelig hjelpe.

Antall pivoter som velges er faktisk det samme uavhengig av algoritmens utførelse. Imidlertid kan arbeid utført per pivot variere avhengig av hva slags splitt du får. I beste tilfelle ender pivoten som er valgt i hvert trinn, medianen i matrisen. Når dette skjer, er det (omtrent) n sammenligninger gjort på det øverste laget av rekursjonen, deretter (omtrent) n ved neste laget fordi det er to underarrays av størrelse n / 2, så er det (omtrent) n ved neste lag fordi det er fire underarrays av størrelse n / 4 osv. Siden det er Θ (log n) lag, og hvert lag gjør Θ (n) arbeid, totalt utført arbeid er Θ (n log n). På den annen side bør du vurdere å velge absolutt minimum for hver matrise som en pivot. Deretter gjøres (omtrent) n sammenligninger på det øverste laget, deretter (omtrent) n – 1 i neste lag, deretter (omtrent) n – 2 i det neste osv. Summen 1 + 2 + 3 + … + n er Θ (n ² ), derav i verste fall.

Håper dette hjelper!

Kommentarer

• Sir, hvordan er det beste tilfellet med heapsort nlogn? Hvis vi anser at alle elementene er identiske, vil kostnaden bare være å itere gjennom alle elementene i matrisen og ikke skifte opp til roten. Så det burde være omega (n) ifølge meg.
• Det er et godt poeng. Jeg antok forskjellige elementer, så jeg oppdaterer dette svaret.

Siden ingen «s virkelig adressert heapSort ennå:

Forutsatt at du bruker en maks bunke representert som en matrise og setter inn dine maksimale elementer bakover i utdata-arrayet / inn i baksiden av arrayet ditt hvis du gjør det på plass , det verste tilfellet input for heapSort er enhver inngang som tvinger deg til å «boble ned» eller repetere hver gang du fjerner et element. Dette skjer hver gang du prøver å sortere et sett uten duplikater. Det vil fortsatt være Θ (n logg n), som templatetypedef sa.

Denne egenskapen innebærer at heapSorts beste tilfelle er når alle elementene er like (Θ (n), siden du ikke trenger å gjenopplive etter hver fjerning, noe som tar logg (n) tid siden maks høyde på dyngen er logg (n)). Det er liksom en elendig / upraktisk sak, og det er derfor den virkelige beste saken for heapsort er Θ (n log n).

Kommentarer

• Poenget ditt med den elendige upraktiske saken ble nettopp spurt i algoritmeklassen min. (pass opp for triksespørsmål.) Selvfølgelig er jeg ‘ fortsatt enig med poenget ditt. og fikk svaret mitt feil som et resultat XD)

• Rask sortering

  Verste tilfelle: $ \ mathcal {O} (n ^ 2) $ . La oss anta at dreieelementet alltid er det rette elementet: Skriv inn et allerede sortert liste med $ n $ -elementer. Så hver partisjonering fører til en liste med $ n-1 $ -elementer og en liste med $ 0 $ -elementer. Selv om du velger pivotelementet tilfeldig , kan du fremdeles være uheldig og alltid velge maksimumsverdien i listen.

  La $ T (n) $ være antall sammenligninger quicksort krever å sortere en liste med $ n $ -elementer. Verste tilfelle: \ begin {align} T (n) = & T (n-1) + n & \ text {($ T (n-1) $ rekursiv, $ n $ til partisjon)} \\ = & \ frac {n (n + 1) } {2} \ in \ mathcal {O} (n) \ end {align}

  Best case: $ \ mathcal {O} (n \ log n) $ . Hvis pivotelementet er valgt på en slik måte, at det partisjonerer listen jevnt:

  \ begin {align} T (n) = & 2 \ T \ left (\ frac {n} {2} \ right) + n & (\ text {2 ganger $ \ frac {n} { 2} $ rekursiv, $ n $ til partisjon)} \\ \ i & \ mathcal {O} (n \ log n) & (\ text {masterteorem}) \ end {align}

• Heap Sort

  Verste fall og best case kompleksitet for haugsortering er begge $ \ mathcal {O} (n \ log n) $ . Derfor trenger sortering $ \ mathcal {O} (n \ log n) $ sammenligninger for alle inngangssett. Kompleksitet av haugsortering:

  \ 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) & (\ tekst {logaritmkvotientregel}) \\ = & \ mathcal {O} (n \ log n) & \ left (\ sum_ {i = 1} ^ {n} \ log i < \ sum_ {i = 1} ^ {n} \ log n = n \ log n \ right) \ end {align }

Kommentarer

• Du har ‘ t svarte på alle OP ‘ spørsmålene, så jeg vil svare på et du savnet; heap sort bruker ikke ‘ t alltid samme antall sammenligninger for et gitt antall elementer. Det verste tilfellet er $ a \, n \ log n $ og det beste tilfellet er $ b \, n \ log n $, der $ a > b $.
• Vær også oppmerksom på at treveisvarianten har lineær best case for enkeltelementinngang.