If you're seeing this message, it means we're having trouble loading external resources on our website.

Ha webszűrőt használsz, győződj meg róla, hogy a *.kastatic.org és a *.kasandbox.org nincsenek blokkolva.

Fő tartalom

Tantárgy/kurzus: Számítástudomány > 1. témakör

4. lecke: Minimumkiválasztásos rendezés
Informatika
Számítástudomány
Algoritmusok
Minimumkiválasztásos rendezés
© 2024 Khan AcademyFelhasználási feltételekAdatkezelési tájékoztatóSüti figyelmeztetés

Minimumkiválasztásos rendezés elemzése

Google Osztályterem
A minimumkiválasztásos rendezés végigveszi a tömb indexeit; minden indexre meghívja az indexOfMinimum és swap függvényeket. Ha a tömb hossza n, akkor a tömbben n index van.
Mivel a ciklus törzse két programsort tartalmaz, azt gondolhatod, hogy a minimumkiválasztásos rendezés során 2n utasítás hajtódik végre. De ez nem igaz! Ne feledd: az indexOfMinimum és a swap függvények, amikor azokat meghívod, ott is programsorok vannak!
Hány programsor hajtódik végre a swap egy hívásakor? A szokásos implementációban három sor, úgyhogy a swap minden egyes meghívása konstans idő alatt fut le.
Hány programsor hajtódik végre az indexOfMinimum egy hívásakor? Itt az indexOfMinimum belsejében levő ciklust kell figyelembe venni. Hányszor fut le a ciklus az indexOfMinimum egy hívása során? Ez függ a résztömb méretétől. Ha a résztömb megegyezik a teljes tömbbel (ez az eset az első kereséskor), akkor a ciklustörzs n-szer fut le. Ha a résztömb 6 hosszúságú, akkor a ciklustörzs 6-szor fut le.
Például tegyük fel, hogy a teljes tömb 8 elemet tartalmaz. Gondold végig, hogy ebben az esetben hogyan működik a minimumkiválasztásos rendezés!
  1. Az indexOfMinimum első hívásakor a tömb minden elemét meg kell vizsgálni, ezért az indexOfMinimum ciklustörzse 8-szor fut le.
  2. Az indexOfMinimum második hívásakor a résztömböt az 1.-től a 7. indexig kell megvizsgálni, úgyhogy az indexOfMinimum ciklustörzse 7-szer fut le.
  3. A harmadik hívás esetén a résztömböt a 2.-tól a 7. indexig vizsgálja; a ciklustörzs 6-szor fut le.
  4. A negyedik hívás alkalmával a résztömböt a 3.-tól a 7. indexig nézi; a ciklustörzs 5-ször fut le.
  5. …
  6. Az indexOfMinimum nyolcadik és egyben utolsó hívásakor a ciklustörzs csak 1-szer fut le.
Ha összeadjuk, hogy az indexOfMinimum ciklustörzse hányszor fut le, akkor ezt kapjuk: 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 36 .

Széljegyzet: Számok összegzése 1-től n-ig

Hogyan lehet gyorsan kiszámítani a 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 összeget? Mutatok egy cseles megoldást. Végezzük el az összeadást egy trükkös sorrendben! Először végezzük el a 8 + 1 műveletet, a legkisebb és a legnagyobb számot összeadva. Az eredmény 9. Ezután jön 7 + 2, a második legnagyobb és második legkisebb szám összege. Érdekes módon megint 9 az eredmény. És 6 + 3? Az is 9. Végül jön 5 + 4. Ennek az eredménye is 9! Összefoglalva a fentieket ezt látjuk:
(8+1)+(7+2)+(6+3)+(5+4)=9+9+9+9=4⋅9=36 .
Négy számpárosunk van és mindegyik 9-et ad eredményül. Ha általánosan fogalmazzuk meg: egész számok sorozatának összeadását az alábbi képlet alapján számolhatjuk ki:
  1. Add össze a legnagyobb és a legkisebb számot!
  2. Szorozd meg a párok számával!
Mi van abban az esetben, ha a sorozatban páratlan számú elem van, és így nem tudod párosítani a számokat? Nem számít! A középső, pár nélkül maradt számot egyszerűen fél párként kell értelmezni. Például adjuk össze a következő sorozatot: 1 + 2 + 3 + 4 + 5. Két teljes párunk van (1 + 5 és 2 + 4, mindkettő 6-ot eredményez), és egy „fél pár” (3, ami a 6 fele), ez 2,5 párt eredményez. Elvégezzük a szorzást: 2,5⋅6=15, és megkapjuk a jó eredményt.
Mi a helyzet, ha 1-től n-ig kell összeadni a számokat? Ezt számtani sorozatnak hívjuk. A legkisebb és a legnagyobb szám összege n+1. Mivel összesen n számunk van, a párok száma n/2 (függetlenül attól, hogy n páros vagy páratlan). Ezért a számok összege 1-től n-ig (n+1)(n/2), ami n2/2+n/2. Próbáld ki ezt a képletet, ahol n=5 és n=8.

A minimumkiválasztásos rendezés futási idejének aszimptotikus elemzése

A minimumkiválasztásos rendezés teljes futási ideje három részből áll össze:
  1. Az indexOfMinimum meghívásaiból adódó futási idő.
  2. A swap meghívásaiból adódó futási idő.
  3. A selectionSort függvény ciklusának további utasításaiból adódó futási idő.
A 2. és 3. pont könnyen meghatározható. Tudjuk, hogy a swap és az egyes függvényhívások futási ideje konstans és n-szer kerül végrehajtásra. Az aszimptotikus jelölésrendszer használatával a swap összes hívásához szükséges idő Θ(n). A selectionSort ciklusában még szerepel tesztelés és a ciklusváltozó növelése, valamint az indexOfMinimum és swap meghívása, amihez konstans idő tartozik minden egyes n iterációban, amihez szintén Θ(n) idő kell.
Ami az 1. részt illeti, az indexOfMinimum összes hívásának futási idejét, a nehezén már túl vagyunk. Az indexOfMinimum-ban található ciklus minden egyes iterációjának futási ideje konstans. Az iterációk száma az első híváskor n, majd n−1, ezután n−2 és így tovább. Láttuk, hogy ez az összeg 1+2+⋯+(n−1)+n egy számtani sorozat, aminek értéke (n+1)(n/2), avagy n2/2+n/2. Ezért az indexOfMinimum hívások összértéke valamilyen konstansszor n2/2+n/2. A Θ-jelölés szerint a konstans tényező elhagyható, és az 1/2 sem számít, valamint az alacsonyabb rendű tag sem. Eredményül tehát azt kaptuk, hogy az indexOfMinimum összes hívásának futási ideje Θ(n2).
A három rész futási idejét összeadva az indexOfMinimum hívások futási ideje Θ(n2), a swap hívásoké Θ(n) és Θ(n) kell a selectionSort ciklusának többi utasításaihoz. A Θ(n2) a szignifikáns rész, így azt mondhatjuk, hogy a minimumkiválasztásos rendezés futási ideje Θ(n2).
Megfigyelhetjük azt is, hogy a minimumkiválasztásos rendezés szempontjából nincs különösen kedvező, vagy különösen kedvezőtlen eset. Az indexOfMinimum-ban található ciklus minden esetben n2/2+n/2 iterációt hajt végre az inputtól függetlenül. Tehát azt állítjuk, hogy a minimumkiválasztásos rendezés futási ideje minden esetben Θ(n2).
Vizsgáljuk meg, hogy a Θ(n2) futási idő hogyan befolyásolja a valós végrehajtás idejét! Mondjuk, hogy a minimumkiválasztásos rendezés megközelítőleg n2/106 másodperc alatt rendez n értéket. Kezdjünk egy viszonylag kis n-nel, mondjuk n=100. Akkor a minimumkiválasztásos rendezés futási ideje körülbelül 1002/106=1/100 másodperc. Ez meglehetősen gyors. De mi van akkor, ha n=1000? Akkor a futási idő már 10002/106=1 másodperc lesz. A tömb 10-szeresére nőtt, de a futási idő 100-szorosára emelkedett. És mi van akkor, ha n=1 000 000? Akkor a rendezéshez szükséges idő 1 000 0002/106=1 000 000 másodperc, ami valamivel több, mint 11,5 nap. Ha a tömb mérete ezerszeresére nő, akkor a futási idő a milliószorosára fog nőni!
Ez a fejezet a Dartmouth Computer Science két professzora, Thomas Cormen és Devin Balkcom, valamint a Khan Academy informatika tanmenetfejlesztő csapatának együttműködésében készült. A tartalom a CC-BY-NC-SA licenc alatt engedélyezett.

Szeretnél részt venni a beszélgetésben?

Jelentkezz be
Még nincs hozzászólás.
Tudsz angolul? Kattints ide, ha meg szeretnéd nézni, milyen beszélgetések folynak a Khan Academy angol nyelvű oldalán.