Beste en slechtste invoer voor heap-sortering en snel sorteren?

heap- Aangezien het beste en het slechtste geval hetzelfde zijn maakt het niet uit in de invoervolgorde? Het aantal vergelijkingen en opdrachten zal altijd hetzelfde zijn? Ik stel me voor dat het in een heap-sortering hetzelfde kan zijn, aangezien het echte werk wordt gedaan bij het invoegen, maar het sorteren gebruikt alleen het verwijderen van de max / min heap? Is dat waarom?

Het aantal gemaakte vergelijkingen kan afhangen van de volgorde waarin de waarden worden gegeven. Het feit dat het beste en het slechtste geval elk Θ (n log n) zijn – ervan uitgaande dat alle elementen verschillend zijn – betekent alleen dat er asymptotisch geen verschil is tussen de twee, hoewel ze kunnen verschillen met een constante factor. Ik heb hier geen simpele voorbeelden van uit mijn hoofd, maar ik geloof dat je inputs kunt construeren waarbij het aantal vergelijkingen verschilt met een constante factor tussen de twee benaderingen. Aangezien de big-O-notatie constanten negeert, wordt dit echter niet “weerspiegeld in de best-case en worst-case-analyse.

snelle sortering- Deze Ik weet het niet zeker. Ik weet niet zeker wat de beste en slechtste situaties hiervoor zijn. Als het een reeds gesorteerde lijst van bijvoorbeeld 10 strings is, zouden we dan niet altijd hetzelfde aantal pivots moeten kiezen om het recursieve algoritme te voltooien? Elke hulp bij deze uitleg zou echt helpen.

Het aantal gekozen draaipunten is inderdaad hetzelfde, ongeacht de uitvoering van het algoritme. Het werk dat per spil wordt gedaan kan echter variëren, afhankelijk van het soort splitsingen dat u krijgt. In het beste geval is het bij elke stap gekozen draaipunt het mediaanelement van de array. Wanneer dit gebeurt, zijn er (ongeveer) n vergelijkingen gedaan op de bovenste laag van de recursie, dan (ongeveer) n op de volgende laag omdat er twee subarrays van grootte n / 2 zijn, dan zijn er (ongeveer) n op de volgende laag omdat er vier submatrices zijn van grootte n / 4, enz. Omdat er Θ (log n) lagen zijn en elke laag Θ (n) werk, het totale uitgevoerde werk is Θ (n log n). Overweeg aan de andere kant om het absolute minimum van elke array als draaipunt te kiezen. Dan worden (ongeveer) n vergelijkingen gedaan op de bovenste laag, dan (ongeveer) n – 1 in de volgende laag, dan (ongeveer) n – 2 in de volgende, etc. De som 1 + 2 + 3 + … + n is Θ (n ² ), vandaar het ergste geval.

Ik hoop dat dit helpt!

Opmerkingen

• Meneer, hoe is het beste geval van heapsort nlogn? Als we beschouwen dat alle elementen identiek zijn, zouden de kosten alleen door alle elementen van de array moeten worden herhaald en niet tot aan de wortel verschuiven. Dus het zou volgens mij omega (n) moeten zijn.
• Dat is een goed punt. Ik ging uit van verschillende elementen, dus ik ga dit antwoord updaten.

Omdat niemand echt geadresseerde heap Sorteer nog:

Ervan uitgaande dat je “max heap gebruikt als een array en je max elementen achterstevoren invoegt in je output array / in de achterkant van je array als je het op zijn plaats doet is de slechtste invoer voor heapSort elke invoer die u dwingt om elke keer dat u een element verwijdert, te “bubbelen” of opnieuw te stapelen. Dit gebeurt elke keer dat u een set probeert te sorteren zonder duplicaten. Het zal nog steeds Θ (n log n), zoals templatetypedef zei.

Deze eigenschap impliceert dat heapSort het beste geval is als alle elementen gelijk zijn (Θ (n), aangezien je niet opnieuw hoeft te stapelen na elke verwijdering, wat log (n) tijd kost sinds de maximale hoogte van de heap is log (n)). Het is echter nogal een belabberd / onpraktisch geval, en daarom is Θ (n log n) het beste geval voor heapsort.

Opmerkingen

• Je punt over het belabberde, onpraktische geval is zojuist gesteld in mijn algoritmenklas. (pas op voor strikvragen.) Natuurlijk ben ik ‘ het nog steeds eens met je punt. ( en kreeg mijn antwoord daardoor verkeerd XD)

• Snel sorteren

  Slechtste geval: $ \ mathcal {O} (n ^ 2) $ . Laten we aannemen dat het pivot-element altijd het meest rechtse element is: voer een al in gesorteerde lijst met $ n $ elementen. Elke partitionering leidt dus naar één lijst met $ n-1 $ elementen en één lijst met $ 0 $ -elementen. Zelfs als u het pivot-element willekeurig kiest , kunt u nog steeds pech hebben en altijd de maximale waarde in de lijst kiezen.

  Laat $ T (n) $ het aantal vergelijkingen quicksort zijn vereist om een lijst te sorteren met $ n $ elementen. In het ergste geval: \ 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}

  Beste case: $ \ mathcal {O} (n \ log n) $ . Als het pivot-element zo wordt gekozen, wordt de lijst gelijkmatig verdeeld:

  \ begin {align} T (n) = & 2 \ T \ left (\ frac {n} {2} \ right) + n & (\ text {2 keer $ \ frac {n} { 2} $ recursief, $ n $ naar partitie)} \\ \ in & \ mathcal {O} (n \ log n) & (\ text {master theorem}) \ end {align}

• Heap sorteren

  De worst case en de best case complexiteit voor heap-sortering zijn beide $ \ mathcal {O} (n \ log n) $ . Daarom heeft heap-sortering $ \ mathcal {O} (n \ log n) $ vergelijkingen nodig voor elke invoerarray. Complexiteit van heap-sortering:

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

Reacties

• Je hebt ‘ t beantwoordde alle OP ‘ vragen, dus ik zal er een beantwoorden die je hebt gemist; heap-sortering gebruikt niet ‘ t altijd hetzelfde aantal vergelijkingen voor een bepaald aantal elementen. Het slechtste geval is $ a \, n \ log n $ en het beste geval is $ b \, n \ log n $, waarbij $ a > b $.
• Merk ook op dat de driewegvariant het beste lineair heeft voor invoer van één element.