Lineaariset ja binaariset hakualgoritmit selitetty

Kyky etsiä tietoja on tärkeä osa tietojenkäsittelytiedettä. Hakualgoritmeja käytetään tietyn kohteen etsimiseen tietojoukosta.

Algoritmit palauttavat loogisen tuloksen (tosi tai epätosi) hakukyselyyn. Niitä voidaan myös muokata antamaan löydetyn arvon suhteellinen sijainti.

Tässä artikkelissa algoritmit keskittyvät määrittämään, onko arvo olemassa.

Lineaariset hakualgoritmit

Lineaarinen haku tunnetaan myös nimellä peräkkäinen haku. Tämän tyyppisessä haussa luettelon jokaisessa arvossa käydään yksitellen järjestyksessä samalla kun tarkistetaan, onko haluttu arvo olemassa.

Algoritmi tarkistaa arvon arvon mukaan, kunnes löytää etsimäsi arvon tai loppuu haettavat arvot. Kun haettavat arvot loppuvat, hakukyselyäsi ei ole luettelossa.

Peräkkäinen hakualgoritmi ottaa parametreiksi arvoluettelon ja halutun kohteen luettelossa. Palautustulos alustetaan muodossa Väärä ja muuttuu Totta kun haluttu arvo löytyy.

Katso esimerkki alla olevasta Python -toteutuksesta:

def linearSearch (mylist, item):

löytynyt = väärä

indeksi = 0

kun taas indeksi

jos minun listani [hakemisto] == kohde:

löydetty = Totta

muu:

indeksi = indeksi+1

paluu löytyi

Algoritmin analyysi

Paras tapaus ilmenee, kun haluttu kohde on luettelon ensimmäinen. Pahin tapaus ilmenee, kun haluttu kohde on luettelon viimeinen (n. Kohta). Siksi lineaarisen haun aika monimutkaisuus on O (n).

Keskimääräinen tapausskenaario yllä olevassa algoritmissa on n/2.

Aiheeseen liittyviä: Mikä on Big-O-merkintä?

Muokattu lineaarinen haku

On tärkeää tietää, että käytetty algoritmi olettaa, että sille annetaan satunnainen luettelo kohteista. Eli luettelokohteet eivät ole erityisessä järjestyksessä.

Oletetaan, että tuotteet olivat tietyssä järjestyksessä, esimerkiksi pienimmästä suurimpaan. Laskennassa olisi mahdollista saavuttaa jonkin verran etua.

Ota esimerkki siitä, että etsit 19 luettelosta: [2, 5, 6, 11, 15, 18, 23, 27, 34]. Kun saavutat 23, kävisi ilmi, että etsittävää kohdetta ei ole luettelossa. Siksi ei enää olisi tärkeää jatkaa muiden luettelokohteiden etsimistä.

Binaariset hakualgoritmit

Olet nähnyt, kuinka järjestetty luettelo voi vähentää tarvittavaa laskentaa. Binaarinen hakualgoritmi hyödyntää tätä tehokkuutta vielä enemmän, kun järjestetty luettelo tuo mukanaan.

Algoritmi alkaa ottamalla tilatun luettelon keskiarvo ja tarkistamalla, onko se haluttu arvo. Jos ei, arvo tarkistetaan, onko se pienempi tai suurempi kuin haluttu arvo.

Jos se on vähemmän, sinun ei tarvitse tarkistaa luettelon alaosaa. Muussa tapauksessa, jos se on suurempi, se siirtyy luettelon yläosaan.

Aiheeseen liittyviä: Mikä on rekursio ja miten sitä käytetään?

Riippumatta siitä, kumpi alaluettelo (vasen tai oikea) valitaan, keskiarvo määritetään uudelleen. Arvo tarkistetaan uudelleen, jos se on vaadittu arvo. Jos ei, tarkistetaan, onko se pienempi vai suurempi kuin pyydetty arvo.

Tämä prosessi toistetaan, kunnes arvo löytyy, jos se on olemassa.

Alla oleva Python -toteutus on tarkoitettu binäärihakualgoritmille.

def binarySearch (mylist, item):

alhainen = 0

korkea = len (mylist) - 1

löytynyt = väärä

kun taas matala <= korkea eikä löydy:

keski = (matala + korkea) // 2

jos mylist [mid] == item:

löydetty = Totta

elif item

korkea = puolivälissä - 1

muu:

alhainen = puolivälissä + 1

paluu löytyi

Algoritmin analyysi

Paras tapaus ilmenee, kun haluttu kohde todetaan keskimmäiseksi. Pahin skenaario ei kuitenkaan ole niin suoraviivainen. Seuraa alla olevaa analyysiä:

Ensimmäisen vertailun jälkeen n/2 kohdetta jää jäljelle. Toisen jälkeen n/4 kohdetta jää jäljelle. Kolmannen jälkeen n/8.

Huomaa, että kohteiden määrä puolittuu, kunnes ne saavuttavat n/2i, missä i on vertailujen määrä. Kaiken jakamisen jälkeen päädymme vain yhteen tuotteeseen.

Tämä tarkoittaa seuraavaa:

n/2i = 1

Siksi binäärihaku on O (log n).

Siirtyminen lajitteluun

Binäärihaussa harkitsimme tapausta, jossa annettu ryhmä oli jo tilattu. Mutta oletetaan, että sinulla oli järjestämätön tietojoukko ja halusit tehdä siitä binaarisen haun. Mitä sinä tekisit?

Vastaus on yksinkertainen: lajittele se. Tietojenkäsittelytieteessä on useita lajittelutekniikoita, jotka on tutkittu hyvin. Yksi näistä tekniikoista, joita voit aloittaa opiskelun, on valinnan lajittelualgoritmi, kun meillä on paljon oppaita, jotka liittyvät myös muihin alueisiin.

Valintalajittelun käyttäminen

Valinnan lajittelu on hieman hankala ymmärtää aloittelijoille, mutta se ei ole liian haastavaa, kun saat asiat vauhtiin.

Lue seuraava

Kirjailijasta