| << 1.4 Algoritmi keerukus | Sisukord | 2 Sorteerimine >> |
Tunni läbimisel:
- Oskan otsida järjendist elementi ja arvutada selle kiirust
- Tean, mis on kahendotsing
- Oskan kahendotsingu algoritmi kirjutada
2.1 Otsimine
Eelmistes peatükis õppimise, kuidas lahendada probleeme algoritmidega ning hindasime nende algoritmide kiirust. Selles tunnis vaatame, kuidas kavala algoritmi abil saab suur interneti veebisait oma rakenduse kasutajate jaoks kiiremaks teha.
Kordamine
Suurel interneti veebisaidil on 300 miljonit kasutajat. Kui uus kasutaja sisse logib, peab ta valima endale kasutajanime, mida pole varem kasutatud. Et seda teha peab veebisaidil olema funktsioon, mis kontrollib, kas sisestatud sõne on kasutajanimena saadaval või mitte. Eeldame, et veebiserveriks olev arvuti suudab võrrelda miljon sõnet sekundis. Kui palju kulub järgneval funktsioonil aega, et teha kindlaks, kas soovitud kasutajanimi on saadaval või mitte?
- 5 minutit
Kahjuks ei ole enamik kasutajaid nõus nii kaua ootama ja lähevad tõenäoliselt konkurendi juurde, kelle veebileht töötab kiiremini. Juhul kui me hoiame andmeid suvalises järjekorras, ei saa me otsingut kuidagi kiiremaks teha, vaid peamegi kõik andmed ükshaaval läbi vaatama. Meie ise inimesena suudame palju vähem sõnu sekundis läbi vaadata, siiski näiteks sõnaraamatust õnnestub meil õige sõna kõigest sekunditega üles leida (Eesti Õigekeelsussõnaraamatus on umbes 130000 sõna). Mis aitab meil sõnaraamatust õige sõna kiiresti üles leida? Mis viisil me seda ära kasutame?
- Sõnaraamatus olevad sõnad on tähestikulises järjekorras sorteeritud, ning seetõttu saame me paljude sõnade võrdlemise vahele jätta.
- Niipea kui me sõnaraamatus mõnda sõna oma otsitava sõnaga võrdleme, saame kohe kõik eespoolsed ja tagapoolsed sõnad välistada. Seega kui me avame sõnaraamatu täpselt keskelt, saame ühe sõna võrdlemisega kohe pool raamatut vaatlemata jätta ning nii igal sammul.
Ülesanne 1
Koosta plokkskeem sõnaraamatust õige sõna otsimiseks. Vajalikud plokid võid ise defineerida, aga skeem peaks sisaldama vähemalt ühte tingimusplokki.
- Ülesande lahendamiseks võid kasutada näiteks järgnevaid plokke:
Sellist algoritmi polnudki kõige lihtsam kirjeldada ning ülesandele lisas keerukust see, et kõigepealt on tarvis üles leida sobiv leht ja seejärel sealt sealt õige sõna. Õnneks on arvutis andmed enamasti järjest ning peab vaid teadma õiget kohta, kust vaadata. Kui sa võtsid sõnaraamatu keskelt lahti, oled aga juba poole lähemal järgmisele algoritmile.
Definitsioon: Kahendotsing on algoritm, sorteeritud järjendist elemendi leidmiseks. Kahendotsing võrdleb järjendi keskmiste elementi otsitava elemendiga. Vastavalt sellele, kas otsitav element on suurem või väiksem, jätkab algoritm otsingut ainult suuremate või väiksemate elementide peal. Seda protsessi korratakse, kuni on leitud õige element, või kuni piirkonnas, millest otsitakse, ei leidu enam ühtegi elementi. Viimasel juhul otsitavat elementi selles järjendis pole.
Näide: Otsime alltoodud sorteeritud järjendist arvu 4. Hallid kaardid tähistavad järjendi elemente ning iga kaardi alla on märgitud ka tema positsioon järjendis. Nagu näha, siis arvu 4 selles järjendis ei leidu ning seega peab samale järjeldusele jõudma ka otsingu algoritm. Esmalt vaatab algoritm järjendi keskmist elementi, kui elemente on paaris arv, valime näiteks väiksema. Joonisel on tähistatud vaadeldav element rohelise noolega.
Kuna otsitav element 4 on väiksem 12, jätkame otsingut ainult järjendi esimse poolega ning kordame täpselt sama protseduuri. Uueks vaadeldavaks elemendiks on 3.
Kuna 3 on suurem kui 4, vaatleme järgmisel ringil ainult kolmest suuremaid elemente, aga 12 väiksemaid. Uueks keskmiseks elemendiks on 5.
Kuna otsitavas piirkonnas pole enam ühtegi elementi, lõpetab algoritm töö ning tagastab, et arvu 4 ei leitud.
Ülesanne 2
Koosta ülesandes 1 kujutatud algoritmi asemele kahendotsingul põhinev algoritm. Alustada võid sellest meetodist:
- Kõige lihtsam on kasutada rekursiooni ja selle sammuna vähendada vaadeldavate elementide hulka.
- Pythonis saab kergesti leida järjendi alguse või lõpu, kasutades koolonit, näiteks:
- users[start:] annab järjendi lõpus olevad elemendid, alustades elemendist indeksiga start.
- users[:end] annab järjendi alguses olevad elemendid, kuni elemendini indeksiga end.
Lisaülesanded
- Kui palju aega kulub ülesandes 2 koostatud kahendotsingu algoritmil aega, et teha kindlaks, kas sellise nimega kasutaja leidub või mitte (samadel tingimustel mis kordamisülesandes)?
- Mis on kahendotsingu ajaline keerukus?
- Täienda kahendotsingu algoritmi selliselt, et see tagastab arvu, mitu korda otsitavat väärtust järjendis on. Näiteks järjendist [1, 2, 4, 4, 6, 8, 8, 8] otsides väärtust 3 annab see algoritm vastuseks 0, aga otsides väärtust 4 antakse vastuseks 2.
Järgmises peatükis vaatame, kuidas järjendit sorteerida.
Mõisted:
- kahendotsing - algoritm, sorteeritud järjendist elemendi leidmiseks.
Viited:
| << 1.4 Algoritmi keerukus | Sisukord | 2 Sorteerimine >> |