Miért gyorsabb a szelekció, mint a buborék?

Minden megadott összetettség igaz, de megadatott Big O jelölésben , így az összes additív érték és konstans elmarad.

A kérdés megválaszolásához nem szükséges d a két algoritmus részletes elemzésére összpontosítsak. Ez az elemzés elvégezhető kézzel, vagy sok könyvben megtalálható. A Knuth számítógépes programozás eredményeit felhasználom.

Az összehasonlítások átlagos száma:

• Buborékfajta : $ \ frac {1} {2} (N ^ 2-N \ ln N – (\ gamma + \ ln2 -1) N) + \ mathcal O (\ sqrt N) $
• Beillesztés rendezése : $ \ frac {1} {4} (N ^ 2-N) + N – H_N $
• Kiválasztás rendezése : $ (N + 1) H_N – 2N $

Ha ezeket a függvényeket ábrázolja, valami ilyesmit kap:

Mint látható, a buborékok rendezése sokkal rosszabb, mivel az elemek száma növekszik, annak ellenére, hogy mindkét rendezési módszernek ugyanaz az aszimptotikus bonyolultság.

Ez az elemzés azon a feltételezésen alapul, hogy az input véletlenszerű – ami lehet, hogy nem mindig igaz. A válogatás megkezdése előtt azonban véletlenszerűen (bármilyen módszerrel) megfertőzhetjük a bemeneti szekvenciát az átlagos eset megszerzéséhez.

Kihagytam az időbonyolultság-elemzést, mert ez a megvalósítástól függ, de hasonló módszerek is alkalmazhatók.

Megjegyzések

• Problémám van a ” vel, véletlenszerűen megengedhetjük a bemeneti szekvenciát az átlagérték “. Miért lehet ezt gyorsabban elvégezni, mint a rendezéshez szükséges idő?
• Bármely számsorozatot megfertőzheti, amihez $ N $ idő kell, ahol $ N $ a szekvencia hossza. ‘ nyilvánvaló, hogy minden összehasonlításon alapuló rendezési algoritmusnak legalább $ \ mathcal O (N \ log N) $ összetettségűnek kell lennie, még akkor is, ha hozzáad $ N $ -ot ‘ s komplexitása nem fog annyira megváltozni ‘. Egyébként nem az idő összehasonlításáról beszélünk, az idő bonyolultsága a megvalósítástól és a gép futásától függ, amint azt a válaszban említettem.
• Azt hiszem, álmos voltam, igazad van, a sorrend lineáris időben megismételhető .
• Mivel $ H_N = \ Theta (log N) $, az összehasonlítási kötése helyes a kiválasztási rendezéshez? Úgy tűnik, hogy ‘ arra utal, hogy átlagosan O (n log n) összehasonlítást végez.
• Gamma = 0,577216 Euler-Mascheroni ‘ s állandó. A vonatkozó fejezet a ” A programozás művészete ” 3. rész 5.2.2. Oldal. 109. és 129. Hogyan rajzolta meg pontosan a buborék rendezési esetet, különös tekintettel az O (sqrt (N)) kifejezésre? Csak elhanyagolta?

Az aszimptotikus költség, vagy $ \ mathcal O $ -jegyzet, a függvény korlátozó viselkedését írja le, mivel az argumentuma a végtelenségig hajlik, vagyis a növekedési sebességéhez.

Maga a függvény, pl. az összehasonlítások és / vagy a swapok száma eltérő lehet két azonos aszimptotikus költségű algoritmus esetében, feltéve, hogy azonos sebességgel nőnek.

Pontosabban, a Bubble sort átlagosan n / 4 dollárt igényel $ swap bejegyzésenként (minden bejegyzést elemenként mozgatunk a kezdeti helyzetből a végső pozícióba, és minden swap két bejegyzést tartalmaz), míg a Selection sort-hoz csak $ 1 $ szükséges (ha a minimum / maximum megtalálható, egyszer felcseréljük) a tömb végéig).

Az összehasonlítások számát tekintve a Bubble sort $ k \ szor n $ összehasonlítást igényel, ahol $ k $ a bejegyzés kezdeti pozíciója és végső pozíciója, amely általában nagyobb, mint $ n / 2 $ az egyenletesen elosztott kezdeti értékeknél. A szortírozáshoz azonban mindig $ (n-1) \ szor (n-2) / 2 $ összehasonlításra van szükség.

Összefoglalva, az aszimptotikus határ jó érzést nyújt abban, hogyan nőnek egy algoritmus költségei a bemeneti mérethez képest, de nem mond semmit a különböző algoritmusok relatív teljesítményéről ugyanazon halmazon belül.

Megjegyzések

• ez még nagyon jó válasz
• melyik könyvet részesíti előnyben?
• @GrijeshChauhan: A könyvek ízlés kérdése, ezért fogadjon el minden ajánlást egy szem sóval. Nekem személy szerint tetszik Cormen, Leiserson és Rivest ‘ s ” Bevezetés az algoritmusokba “, amely számos témában jó áttekintést nyújt, és Knuth ‘ s ” A számítógépes programozás művészete ” sorozat, ha további információkra van szüksége az összes témáról. Érdemes ellenőrizni, hogy korábban feltették-e már a könyvek kérdését, vagy tegye fel, ha nem ‘ t.
• Számomra harmadik bekezdés a válaszod a tényleges válasz. Nem a nagy bemenetek grafikonjai, amelyeket egy másik válasz ad meg.

A buborékok rendezése több csereidőt használ, míg a szelekciós rendezés ezt elkerüli.

A válogatás használatakor legfeljebb n felcserélhető. de a buborék rendezés használatakor szinte n*(n-1) felcserél. És nyilvánvaló, hogy az olvasási idő még memóriában is kevesebb, mint az írás ideje. Az idő és az egyéb futási idő összehasonlítása figyelmen kívül hagyható. Tehát a csereidő a probléma kritikus szűk keresztmetszete.

Megjegyzések

• Szerintem Bartek másik válasza ésszerűbb, de ‘ nem tudok szavazni vagy megjegyzés … BTW szerintem az írási idő még mindig nagyobb hatással van, és remélem, hogy ezt figyelembe tudja venni, ha ezt meglátja és egyetért.
• Nem hagyhatja egyszerűen figyelmen kívül az összehasonlítások számát, mivel vannak olyan esetek, amikor az idő Két elem összehasonlítására fordított összeg messze meghaladhatja a két elem cseréjére fordított időt. Vegyünk egy összekapcsolt listát a rendkívül hosszú húrokról (mondjuk egyenként 100 ezer karakter). Az egyes karakterláncokban való olvasás sokkal tovább tart, mint a mutató-hozzárendelés.
• @IrvinLim Úgy gondolom, hogy igazad lehet, de lehet, hogy látnom kell a statisztikai adatokat, mielőtt meggondolnám magam.