Bedste og værre tilfælde input til heap sortering og hurtig sortering?

bunke- Da de bedste og værste tilfælde er de samme betyder det ikke noget om rækkefølgen for input? Antallet af sammenligninger og opgaver vil altid være det samme? Jeg forestiller mig, at det i en dyngsort kan være det samme, da det virkelige arbejde udføres i indsættelsen, men sorteringen bruger kun fjernelse af max / min bunke? Er det derfor?

Antallet af sammenligninger, der foretages, kan faktisk afhænge af rækkefølgen, i hvilken værdierne er angivet. Det faktum, at det bedste og værste tilfælde hver er Θ (n log n) – forudsat at alle elementer er forskellige – betyder kun, at asymptotisk der ikke er nogen forskel mellem de to, selvom de kan adskille sig med en konstant faktor. Jeg har ikke nogen enkle eksempler på dette fra toppen af mit hoved, men jeg tror, at du kan konstruere input, hvor antallet af sammenligninger adskiller sig med en konstant faktor mellem to tilgange. Da big-O-notation ignorerer konstanter, afspejles dette dog ikke i bedste-case og worst-case analyse.

hurtig sortering – Denne Jeg ved det ikke helt sikkert. Jeg er ikke sikker på, hvad de bedste tilfælde og værste tilfælde er for dette. Hvis det for eksempel er en allerede sorteret liste med 10 strenge, skulle vi ikke altid vælge den samme mængde drejninger for at få den rekursive algoritme komplet? Enhver hjælp til denne forklaring vil virkelig hjælpe.

Antallet af valgte drejninger er faktisk det samme uanset udførelsen af algoritmen. Imidlertid kan arbejdet udført pr. Drejning variere afhængigt af hvilken slags opdelinger du får. I bedste fald ender den drejning, der vælges ved hvert trin, medianen af arrayet. Når dette sker, er der (nogenlunde) n sammenligninger udført på det øverste lag af rekursionen, derefter (omtrent) n ved det næste lag, fordi der er to underarrangementer i størrelse n / 2, så er der (omtrent) n ved den næste lag, fordi der er fire underarrangementer i størrelse n / 4 osv. Da der er Θ (log n) lag, og hvert lag gør Θ (n) arbejde, det samlede udførte arbejde er Θ (n log n). På den anden side skal du overveje at vælge det absolutte minimum for hver matrix som en drejetap. Derefter (omtrent) n sammenlignes der ved det øverste lag, derefter (omtrent) n – 1 i det næste lag, derefter (omtrent) n – 2 i det næste osv. Summen 1 + 2 + 3 + … + n er Θ (n ² ), deraf det værste tilfælde.

Håber det hjælper!

Kommentarer

• Sir, hvordan er det bedste tilfælde af heapsort nlogn? Hvis vi anser alle elementer for at være identiske, vil omkostningerne bare gentage sig gennem alle elementerne i arrayet og ikke skifte op til rod. Så det burde være omega (n) ifølge mig.
• Det er et godt punkt. Jeg antog forskellige elementer, så jeg opdaterer dette svar.

Da ingen “s virkelig adresseret til heapSort endnu:

Forudsat at du bruger en maksimal bunke repræsenteret som en matrix og indsætter dine max-elementer baglæns i dit output-array / i bagsiden af din array, hvis du gør det på plads , det værste tilfælde input til heapSort er ethvert input, der tvinger dig til at “boble ned” eller genoprette hver gang du fjerner et element. Dette sker hver gang du prøver at sortere et sæt uden dubletter. Det vil stadig være Θ (n log n), som templatetypedef sagde.

Denne egenskab indebærer, at heapSort s bedste tilfælde er, når alle elementer er ens (Θ (n), da du ikke behøver at genoplive efter hver fjernelse, hvilket tager log (n) tid siden bunkens maksimale højde er log (n)). Det er dog en elendig / upraktisk sag, hvorfor det rigtige bedste tilfælde for heapsort er Θ (n log n).

Kommentarer

• Dit punkt på den elendige upraktiske sag blev netop stillet i min algoritmeklasse. (pas på trickspørgsmål.) Selvfølgelig er jeg ‘ stadig enig med dit punkt. ( og fik mit svar forkert som et resultat XD)

• Hurtig sortering

  Værst: $ \ mathcal {O} (n ^ 2) $ . Lad os antage, at drejningselementet altid er det rigtigste element: Indtast et allerede sorteret liste med $ n $ -elementer. Så hver partitionering fører til en liste med $ n-1 $ -elementer og en liste med $ 0 $ -elementer. Selvom du vælger drejelementet tilfældigt , kan du stadig være uheldig og altid vælge den maksimale værdi på listen.

  Lad $ T (n) $ være antallet af sammenligninger quicksort kræver at sortere en liste med $ n $ -elementer. Værste tilfælde: \ begin {align} T (n) = & T (n-1) + n & \ text {($ T (n-1) $ rekursiv, $ n $ til partition)} \\ = & \ frac {n (n + 1) } {2} \ in \ mathcal {O} (n) \ end {align}

  Bedste tilfælde: $ \ mathcal {O} (n \ log n) $ . Hvis drejningselementet vælges på en sådan måde, at det partitionerer listen jævnt:

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

• Heap Sort

  Det værste tilfælde og den bedste case-kompleksitet for bunksortering er begge $ \ mathcal {O} (n \ log n) $ . Derfor skal sortering af bunke $ \ mathcal {O} (n \ log n) $ sammenligninger for ethvert input-array. Kompleksitet af bunksortering:

  \ 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 {logaritme kvotientregel}) \\ = & \ 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 besvarede alle OP ‘ s spørgsmål, så jeg vil svare på en, du savnede; heap sort bruger ikke ‘ t altid det samme antal sammenligninger for et givet antal elementer. Det værste tilfælde er $ a \, n \ log n $ og det bedste tilfælde er $ b \, n \ log n $, hvor $ a > b $.
• Bemærk også, at trevejsvariant har lineær bedste case for enkeltelementinput.