Fő tartalom
Számítástudomány
Beszúró rendezés elemzése
A minimumkiválasztásos rendezéshez hasonlóan a beszúró rendezés is ciklusban halad végig a tömbindexeken. Meghívja az indexekre. Ahogy az
insert
-et az indexOfMinimum
minden egyes meghívása a rendezett résztömb méretétől függően valamennyi időt vesz igénybe, ez az insert
hívásaira is igaz. Tulajdonképpen az előző mondatban a „vesz” szó helyett a „vehet” szót kellene használni, mindjárt látni fogjuk, miért.Vegyük azt a helyzetet, amikor az elemű résztömbbe szúrunk be egy értéket, akkor előfordulhat, hogy az összes elemet arrébb kell csúsztatni eggyel. Ahelyett, hogy pontosan kiszámolnánk, hány programsorra van szükségünk egy elem kulccsal való összevetéséhez és az elem csúsztatásához, maradjunk annyiban, hogy ehhez konstans idő kell, amit jelöljünk -vel. Úgyhogy maximum sor végrehajtására van szükség egy hosszúságú résztömbbe való beszúráshoz.
insert
hívásakor a beszúrandó érték a résztömb minden eleménél kisebb. Például ha 0-t szúrunk be a [2, 3, 5, 7, 11] résztömbbe, akkor a résztömb minden egyes elemét eggyel jobbra kell csúsztatni. Általánosságban, ha egy Tegyük fel, hogy az . Második alkalommal . A harmadik alkalommal . És így tovább, egészen az utolsóig, amikor . Ezért a rendezett résztömbbe való beillesztés összideje így alakul:
insert
minden egyes hívásakor a beszúrandó érték kisebb a tőle balra található résztömb minden egyes eleménél. Amikor először hívjuk meg az insert
-et, Ez az összeg számtani sorozatot alkot, ami -ig megy helyett. Használjuk a számtani sorozatra vonatkozó képletet, ez alapján a rendezett résztömbbe való beszúrás összideje:
Θ-jelölést alkalmazva elhagyjuk az alacsonyabb rendű tagot és a konstans tényezőket ( és 1/2), így azt kapjuk, hogy a beszúró rendezés futási ideje ebben az esetben .
Lefuthat a beszúró keresés -nél rövidebb idő alatt? A válasz igen. Tegyük fel, hogy ez a kiinduló tömbünk: [2, 3, 5, 7, 11], ahol a rendezett résztömb az első négy elem, és a beszúrandó érték 11. Az első vizsgálatnál azt találjuk, hogy 11 nagyobb, mint 7, úgyhogy a résztömb egy elemét se kell jobbra csúsztatni. Akkor az -szer hívjuk meg, ha minden híváshoz konstans idő kell, akkor a beszúró rendezéshez szükséges teljes idő lesz, ami , nem .
insert
adott hívása csak konstans ideig tart. Tegyük fel, hogy az insert
minden egyes hívása csak konstans időt vesz igénybe. Lévén, hogy az insert
-et Előfordulhatnak ezek az esetek? Elképzelhető, hogy az . Mit jelent az, hogy egy elem kisebb a tőle balra levő minden elemnél? A kiinduló tömb visszafelé rendezett sorrendben van, például [11, 7, 5, 3, 2]. Ebből következik, hogy a beszúró rendezés esetében a visszafelé rendezett tömb a legrosszabb eset.
insert
minden egyes hívásakor a résztömb minden elemét jobbra kell csúsztatni? Lehet olyan eset, amikor az insert
hívásakor egyetlen elemet se kell elcsúsztatni? Mindkét kérdésre a válasz igen. Az insert
hívásakor abban az esetben kell minden elemet jobbra csúsztatni, ha a beillesztendő kulcs kisebb a tőle balra eső összes elemnél. Ha minden elem kisebb az összes, tőle balra található elemnél, akkor a beszúró rendezés futási ideje Mi a helyzet az ellenkező esettel? Az . Ez a helyzet akkor fordul elő, ha a kiinduló tömb már rendezett, úgyhogy a beszúró rendezés esetén a legjobb eset, ha a kiinduló tömb már rendezett sorrendben van.
insert
hívásakor akkor nem kell egyetlen elemet se elcsúsztatni, ha a beillesztendő kulcs nagyobb vagy egyenlő a tőle balra található összes elemnél. Azaz ha minden elem nagyobb vagy egyenlő a tőle balra található összes elemnél, akkor a beszúró rendezés futási ideje Mit mondhatunk még a beszúró rendezés futási idejéről? Tegyük fel, hogy a kiinduló tömb sorrendje véletlenszerű. Akkor átlagban azt várjuk, hogy minden elem a tőle balra levő elemek felénél lesz kisebb. Ebben az esetben átlagosan az elemet tartalmazó résztömb esetén elemet csúsztat el. A futási idő a legrosszabb idő fele lesz. De az aszimptotikus jelölésnél, ahol a konstans együttható nem számít, az átlagos eset futási ideje továbbra is lesz, ugyanúgy, mint a legrosszabb esetben.
insert
egy hívása egy Mi van abban az esetben, amikor a kiinduló tömb már „majdnem rendezett”: amikor minden elem maximum egy előre megadott konstans távolságra van (mondjuk 17) a rendezett tömbben elfoglalt helyétől? Akkor az elemű résztömb esetében maximum idő szükséges. Ez összesen az hívását jelenti futási idővel, ami , és ez megegyezik a legjobb esethez szükséges idővel. Ebből következik, hogy a beszúró rendezés a majdnem rendezett tömb esetében gyors lesz.
insert
minden hívása maximum 17 elemet fog arrébb csúsztatni, így az insert
egy hívásához egy insert
Összességében a beszúró rendezés futási ideje:
- Legrosszabb eset:
. - Legjobb eset:
. - Átlagos eset véletlen eloszlású tömb esetében:
. - „Majdnem rendezett” tömb esetén:
.
Ha minden esetre kiterjedően általánosan meg kell határoznunk a beszúró rendezés futási idejét, akkor csak annyit mondhatunk, hogy az idő alatt fut le. Nem mondhatod azt, hogy minden esetben a futási idő, mivel a legjobb esetben a futási idő, és azt sem mondhatod, hogy minden esetben alatt fut le, mert a legrosszabb esetben a futási idő.
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?
Még nincs hozzászólás.