Nejlepší a nejhorší případy pro třídění haldy a rychlé třídění?

halda – Protože nejlepší a nejhorší případ jsou stejné nezáleží na pořadí zadání? Počet srovnání a přiřazení bude vždy stejný? Představuji si, že v hromádce to může být stejné, protože skutečná práce se provádí při vložení, ale třídění používá pouze odstranění halda max / min? Je to důvod?

Počet skutečně provedených srovnání může záviset na pořadí, ve kterém jsou hodnoty uvedeny. Skutečnost, že nejlepší a nejhorší případ jsou každý Θ (n log n) – za předpokladu, že jsou všechny prvky odlišné – pouze znamená, že asymptoticky neexistuje žádný rozdíl mezi těmito dvěma, i když se mohou lišit konstantním faktorem. Nemám žádné jednoduché příklady tohoto, ale věřím, že můžete vytvořit vstupy, kde se počet srovnání liší konstantním faktorem mezi dva přístupy. Protože notace big-O ignoruje konstanty, není to v analýze nejlepších a nejhorších případů zohledněno.

rychlé třídění – toto Nevím jistě. Nejsem si jistý, jaké jsou nejlepší a nejhorší případy. Pokud by to byl již seřazený seznam 10 řetězců, nemuseli bychom vždy zvolit stejné množství čepů, abychom získali rekurzivní algoritmus? Jakákoli pomoc s tímto vysvětlením by skutečně pomohla.

Počet zvolených čepů je skutečně stejný bez ohledu na provedení algoritmu. Odvedená práce pro každý pivot se však může lišit podle toho, jaký druh rozdělení získáte. V nejlepším případě je pivot zvolený v každém kroku středním prvkem pole. Když k tomu dojde, v horní vrstvě rekurze je provedeno (zhruba) n srovnání, poté (zhruba) n v další vrstvě, protože existují dvě podskupiny velikosti n / 2, pak existuje (zhruba) n v další vrstva, protože existují čtyři podskupiny velikosti n / 4 atd. Protože existují Θ (log n) vrstvy a každá vrstva má Θ (n) práce, celková vykonaná práce je Θ (n log n). Na druhou stranu zvažte, že jako pivot zvolíte absolutní minimum každého pole. Pak (zhruba) se provede n srovnání v horní vrstvě, poté (zhruba) n – 1 v další vrstvě, poté (zhruba) n – 2 v další atd. Součet 1 + 2 + 3 + … + n je Θ (n ² ), tedy nejhorší případ.

Doufám, že to pomůže!

Komentáře

• Pane, jaký je nejlepší případ nonsportu haldy? Pokud vezmeme v úvahu, že všechny prvky jsou identické, pak by cena byla pouze iterací všemi prvky pole a bez posunu nahoru do kořene. Podle mě by to tedy mělo být omega (n).
• To je dobrý bod. Předpokládal jsem odlišné prvky, takže tuto odpověď aktualizuji.

Protože nikdo není skutečně adresováno heapSort dosud:

Za předpokladu, že používáte maximální haldu představovanou jako pole a vkládáte maximální prvky zpět do výstupního pole / do zadní části vašeho pole, pokud to děláte na místě , nejhorším vstupem pro heapSort je jakýkoli vstup, který vás donutí „vybublávat“ nebo znovu zrecyklovat pokaždé, když odstraníte prvek. To se stane pokaždé, když se snažíte setřídit sadu bez duplikátů. Bude to stále Θ (n log n), jak řekl templatetypedef.

Tato vlastnost naznačuje, že nejlepším případem heapSortu je situace, kdy jsou všechny prvky stejné (Θ (n), protože po každém odebrání nemusíte znovu zpracovávat, což od doby, kdy maximální výška haldy je log (n)). Je to ale trochu mizerný / nepraktický případ, a proto je nejlepším případem heapsortu Θ (n log n).

Komentáře

• Váš názor na mizerný nepraktický případ byl právě položen v mé třídě algoritmů. (pozor na trikové otázky.) Samozřejmě, že ‚ stále souhlasím s vaším názorem. ( a výsledkem je moje odpověď špatně XD)

• Rychlé řazení

  Nejhorší případ: $ \ mathcal {O} (n ^ 2) $ . Předpokládejme, že pivotní prvek je vždy nejvíce vpravo: Zadejte již seřazený seznam s prvky $ n $ . Každé rozdělení tedy vede k jednomu seznamu s prvky $ n-1 $ a jeden seznam s prvky $ 0 $ . I když náhodně vyberete otočný prvek , stále můžete mít smůlu a v seznamu vždy vyberte maximální hodnotu.

  Nechť $ T (n) $ je počet rychlých srovnání srovnání vyžaduje třídění seznamu s prvky $ n $ . Nejhorší případ: \ begin {align} T (n) = & T (n-1) + n & \ text {($ T (n-1) $ rekurzivní, $ n $ na část)} \\ = & \ frac {n (n + 1) } {2} \ in \ mathcal {O} (n) \ end {align}

  Nejlepší případ: $ \ mathcal {O} (n \ log n) $ . Pokud je prvek pivot zvolen tak, že rozděluje seznam rovnoměrně:

  \ begin {align} T (n) = & 2 \ T \ left (\ frac {n} {2} \ right) + n & (\ text {2krát $ \ frac {n} { 2} $ rekurzivní, $ n $ na oddíl)} \\ \ in & \ mathcal {O} (n \ log n) & (\ text {master theorem}) \ end {align}

• Heap Sort

  Nejhorší případ a nejlepší případ složitosti pro řazení haldy jsou oba $ \ mathcal {O} (n \ log n) $ . Proto řazení haldy vyžaduje $ \ mathcal {O} (n \ log n) $ srovnání pro jakékoli vstupní pole. Složitost řazení haldy:

  \ begin {align} & \ mathcal {O} (n) & (\ text {build $ (1, n) $ halda}) \\ + & \ 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 {pravidlo logaritmu kvocientu)) \\ = & \ mathcal {O} (n \ log n) & \ left (\ sum_ {i = 1} ^ {n} \ log i < \ sum_ {i = 1} ^ {n} \ log n = n \ log n \ right) \ end {zarovnat }

Komentáře

• Nemáte ‚ t neodpověděl na všechny OP ‚ s otázky, takže odpovím na jednu, kterou jste zmeškali; třídění haldy nepoužívá ‚ vždy stejný počet srovnání pro daný počet prvků. Nejhorší případ je $ a \, n \ log n $ a nejlepší případ je $ b \, n \ log n $, kde $ a > b $.
• Upozorňujeme, že třícestná varianta má lineární nejlepší případ pro vstup jednoho prvku.