Proč je výběr rychlejší než bublinový?

Všechny zadané složitosti jsou pravdivé, jsou však uvedeny v Velké notaci , takže jsou vynechány všechny aditivní hodnoty a konstanty.

Abychom vám mohli odpovědět na vaši otázku, potřebujeme d zaměřit se na podrobnou analýzu těchto dvou algoritmů. Tuto analýzu lze provést ručně nebo ji najdete v mnoha knihách. Budu používat výsledky z Knuthova umění počítačového programování .

Průměrný počet srovnání:

• Řazení bublin : $ \ frac {1} {2} (N ^ 2-N \ ln N – (\ gamma + \ ln2 -1) N) + \ mathcal O (\ sqrt N) $
• Třídění vložení : $ \ frac {1} {4} (N ^ 2-N) + N – H_N $
• Selection selection : $ (N + 1) H_N – 2N $

Nyní, když vykreslíte tyto funkce, dostanete něco jako toto:

Jak vidíte, třídění bublin je mnohem horší, protože se zvyšuje počet prvků, přestože obě metody řazení mají stejnou asymptotiku složitost.

Tato analýza je založena na předpokladu, že vstup je náhodný – což nemusí být vždy pravda. Než však začneme třídit, můžeme náhodně permutovat vstupní sekvenci (pomocí jakékoli metody), abychom získali průměrný případ.

Vynechal jsem analýzu časové složitosti, protože záleží na implementaci, ale lze použít podobné metody.

Komentáře

• Mám problém s “ můžeme náhodně permutovat vstupní sekvenci, abychom získali průměrný případ „. Proč je to možné udělat rychleji, než je čas potřebný k třídění?
• Můžete permutovat libovolnou posloupnost čísel, která bude trvat $ N $ čas, kde $ N $ je délka sekvence. Je ‚ zřejmé, že jakýkoli srovnávací algoritmus založený na komparaci musí mít alespoň $ \ mathcal O (N \ log N) $ složitost, takže i když k tomu přidáte $ N $ ‚ s složitost se tolik nezmění ‚. Každopádně mluvíme o komparaci, ne o čase, časová složitost závisí na implementaci a běžícím stroji, jak jsem zmínil v odpovědi.
• Myslím, že jsem byl ospalý, máte pravdu, sekvenci lze permutovat v lineárním čase .
• Vzhledem k tomu, že $ H_N = \ Theta (log N) $, je vaše srovnání vázáno správně pro výběr? Vypadá to, že ‚ naznačujete, že průměrně provádí srovnání O (n log n).
• Gamma = 0,577216 je Euler-Mascheroni ‚ s konstanta. Příslušnou kapitolou je “ Umění programování “ díl 3, část 5.2.2, str. 109 a 129. Jak jste přesně vykreslili případ třídění bublin, zejména termín O (sqrt (N))? Zanedbal jste to?

Asymptotická cena neboli poznámka $ \ mathcal O $, popisuje omezující chování funkce, protože její argument má sklon k nekonečnu, tj. její rychlost růstu.

Samotná funkce, např. počet srovnání a / nebo swapů se může u dvou algoritmů se stejnou asymptotickou cenou lišit, za předpokladu, že rostou se stejnou rychlostí.

Konkrétněji Bubble sort vyžaduje v průměru $ n / 4 $ swapů na záznam (každý záznam je přesunut elementárně z jeho počáteční polohy na jeho konečnou pozici a každý swap zahrnuje dva záznamy), zatímco Selection sort vyžaduje pouze $ 1 $ (jakmile je nalezeno minimum / maximum, je zaměněno jednou na konec pole).

Co se týče počtu srovnání, Bubble sort vyžaduje $ k \ krát n $ srovnání, kde $ k $ je maximální vzdálenost mezi počáteční pozicí záznamu a jeho konečná pozice, která je obvykle větší než $ n / 2 $ pro rovnoměrně rozložené počáteční hodnoty. Třídění výběru však vždy vyžaduje srovnání $ (n-1) \ times (n-2) / 2 $.

Stručně řečeno, asymptotický limit vám dává dobrý pocit z toho, jak náklady na algoritmus rostou s ohledem na velikost vstupu, ale neříká nic o relativním výkonu různých algoritmů v rámci stejné sady.

Komentáře

• toto je dokonce velmi dobrá odpověď
• kterou knihu preferujete?
• @GrijeshChauhan: Knihy jsou věcí vkusu, proto je každé doporučení přijměte s rezervou. Osobně se mi líbí Cormen, Leiserson a Rivest ‚ s “ Úvod do algoritmů „, který poskytuje dobrý přehled o řadě témat a Knuth ‚ s “ Umění počítačového programování “ série, pokud potřebujete více / všechny podrobnosti o konkrétním tématu. Možná budete chtít zkontrolovat, zda zde již byla položena otázka knih, nebo tuto otázku zveřejnit, pokud nemá ‚ t.
• Pro mě třetí odstavec v vaše odpověď je skutečná odpověď. Ne grafy pro velké vstupy uvedené v jiné odpovědi.

Třídění bublin používá více výměnných časů, zatímco výběr se tomu vyhne.

Při použití výběru třídí nejvýše n. ale při použití třídění bublin vymění téměř n*(n-1). A doba čtení je samozřejmě kratší než doba zápisu i v paměti. Porovnávací čas a další provozní dobu lze ignorovat. Časy výměny jsou tedy kritickým problémem problému.

Komentáře

• Myslím si, že druhá odpověď Barteka je rozumnější, ale nemohu ‚ hlasovat nebo komentář … BTW Stále si myslím, že čas na psaní má větší vliv a doufám, že to může vzít v úvahu, pokud to uvidí a souhlasí.
• Nemůžete jednoduše ignorovat řadu srovnání, protože existují případy použití, kdy čas vynaložené na porovnání dvou položek může daleko přesáhnout čas strávený výměnou dvou položek. Zvažte propojený seznam extrémně dlouhých řetězců (řekněme každý po 100 000 znaků). Čtení v každém řetězci by trvalo mnohem déle než změna přiřazení ukazatele.
• @IrvinLim Myslím, že máte pravdu, ale možná si budu muset prohlédnout statistická data, než si to rozmyslím.