Algoritmusok sebessége

Az a baj, hogy ha van benne egy k hosszúságú rendezett részsorozat, akkor ha peched van, akkor ez akár k^2-el is megdobhatja a futásidőt. Ezért tud veszélyes lenni a naiv QuickSort...


Na igen, ez az, ami nagyon gyorsá teszi.
Plusz mellé szekvenciálisan nyúlkál az elemekhez, úgyhogy a cache is jól érzi magát.
Egyébként épp ez utóbbi miatt a randomizált quicksort valamivel lassabban működik nagy adatsorokon, mert a random ugrások miatt (pivot kiolvasása) megnő a valószínűsége +1 cache missnek. (Arról nem is beszélve, hogy le is kell generálni a véletlenszámot, bár azt szerintem nyugodtan vehetjük elhanyagolható időnek. Ide nem kell semmi durva generátor)



Mondjuk itt megteheted, hogy előre kiszámoltatod az összes expressiont, majd azt rendezed... Igaz, ez megdobja a memóriahasználatot egy O(n)-el...

Hu tenyleg, random pivot.
Igazsag szerint csak az tunt nekem fel, hogy 300ezer elemnél egy ilyen szituacioban durvan belassult. A worst case azert tulzas, de ugy mondanam, hogy az egy meglepoen bad case volt.

Ami nekem nagyon tetszik a qsortban, hogy az ido 99%-aban az oszzehasonlitasoknak csak az egyik elemét kell mindig elérni, a masik hosszu ideig 'cache'-olhato. Amikor egy expressiont kellett evalualni a rendezeshez, akkor ez a tulajdonsaga a qsortnak nagyon jol jott.

Ez mondjuk attól függ, hogy hogy választod a pivot elementet.
Ha például a legegyszerűbb módon mindig a legelsőt választod, akkor az alábbi példát majdnem a worst-case (a teljesen rendezett a worst-case).
De például a randomized quicksort-nál ezt már elég jól lehet kerülni és elhanyagolható a valószínűsége, hogy akárcsak meg is közelítse az O(n^2) futásidőt...

Ja, nagyon fontos az input.

Ha jol emlekszem, ez peldaul egy quicksort worst case (nagyon regen belefutottam, asszem valami ilyesmi volt): 1,2,3,4,5,6,7,8,9,0 Ilyen adatokkon lassabb lesz, mint a bubble sort.

vannak erre vonatkozó matematikai eszközök, a programok aszimptotikus bonyolultságvizsgálata körül keresgélj (pl. http://en.wikipedia.org/wiki/Asymptotic_computational_complexity)

persze ez elsősorban elmélet. a gyakorlatban a legcélravezetőbb az, amit Mekkelek5 írt, meg kell mérni. ezzel meg az lesz a baj, hogy az adott implementációt és környezetet is méri, meg a tesztadatokat, stb., úgyhogy ebből meg általános igazságokat nem lehet levonni.

De még ha igaz lenne... akkor sem igaz.

Legfeljebb általános esetekre lehetne kijelenteni valamit, olyan meg nincs

Minden esetben van az adatoknak szerkezete, jellemzői, aztán a környezetnek is van jellege (memória, háttértár, cpu mennyiség, sebesség, kihasználtság, akár még karakterisztika is )

Szóval mint minden esetben, egy szint (igény) felett ez is egy külön tudomány.

" rendezésre a QuickSort a leggyorsabb"

Megint egy kijelentés....


Rendezőalgoritmusok - szemléletesen ábrázolva - Médiatár - Prog.Hu

Azt tudod bizonyítani, hogy az ismert eljárások közül a tesztkörnyezetben melyik a leggyorsabb. Leméred és kész. De ez nem bizonyíték arra, hogy MINDEN feltételek mellett az a leggyorsabb, és azt sem hogy 1 hét vagy 1 év múlva nem lesz annál hatékonyabb, vagy nem lesz rá célhardver (pl tömb rendezésre, vagy fa bejárásra).

A szoftver és hardver környezet is változik, fejlődik, esetleg a programozás technika is. (Pl kitalálod, hogy nem is kell rendezned azt a tömböt, megoldod e nélkül is a feladatot.)

Nem ez a leggyorsabb. Kb egy elterjedt library se (csak) QuickSort-ot használ, hanem különböző hibrid algoritmusokat. [1]

Egyébként is a QuickSort worst-case komplexitása O(n^2), ennél pl helyből jobb a Mergesorté.

Nagyon ritka esetekben egyébként bizonyítható is egy adott algoritmusról, hogy az a létező legjobb az adott általános problémára és architektúrára+konfigurációra (ez utóbbi kettő rendkívül fontos), de az ilyen nagyon-nagyon ritka. Specializált esetekre meg a legtöbbször lehet még gyorsabbat kitalálni.


Visszatérve a rendezésre, itt megint külön alkategória az összehasonlító rendezés (amire a QuickSort például egy példa). Itt könnyedén bizonyítható, hogy mindig minimum O(n*log n) lépésre van szükség az általános problémánál.
De ott vannak a nem összehasonlító rendezések, mint például a bucket-sort, ami O(n) idő alatt végez.


Visszatérve a kérdésre:
Igen, elméletileg lehetséges, de nagyon ritka (és kb kizárólag csak nagyon egyszerű problémáknál).
Sokkal gyakoribb az (bár így is nagyon ritka), hogy bizonyítod egy algoritmusról, hogy aszimptotikusan optimális. Ilyen például a merge-sort (míg a quicksort nem). Ez azonban nem azt jelenti, hogy ez a való életben is, mai számítógépen megvalósítva igaz (ezért gyorsabb általában a quicksort a merge-sort-nál).

Generikus válasz nincs a kérdésedre, egy külön szakterület a számítástudományon belül az algoritmusok műveletigényének elemzése.

Azért az utolsó kérdésedre tudok válaszolni: ha egy bináris fát a 'szokott módon' reprezentálunk (vagyis a szülőben van két mutató a gyerekeire', akkor egy rendezett fában a keresés leggyorsabb (és egyetlen lehetséges) módja az, amit leírtál.

Üdvözlet,

 többségünk gyakran használ valamilyen algoritmust munkája során. Pl. keresési
algoritmust, rendezést, stb. Ezekre leginkább sok évvel ezelőtt kitalált algoritmusokat használunk. Arra volnék kiváncsi, hogy van arra bizonyitási módszer, hogy egy adott algoritmusnál nincs jobb ? Pl. rendezésre a QuickSort a leggyorsabb (azt hiszem). De bizonyitható, hogy ennél nem lehet gyorsabbat kitalálni ? Vagy pl. rendezett bináris fában való keresésre nem lehet gyorsabbat kitalálni, mint azt, hogy "balra és jobbra nézek, majd  ennek ismeretében valamelyik irányba egy szintet lejebb megyek, stb." ?

üdv, PedroIsmerőse