Lineaarinen haku vs. binaarihaku
Sisältö
- Sisältö: Ero lineaarisen ja binaarisen haun välillä
- Vertailutaulukko
- Binaarihaku
- Keskeiset erot
- johtopäätös
- Selittävä video
Ero lineaarisen ja binaarisen haun välillä on, että lineaarisessa haussa jokainen elementti tarkistetaan ja verrataan ja lajitellaan, kun taas binaarisessa haussa lajiteltava luettelo jaetaan kahteen osaan ja lajitellaan sitten. Etsiminen ja lajittelu ovat kaksi pääkonseptia tietokoneohjelmoinnissa. Monia algoritmeja käytetään etsimiseen ja lajitteluun, mutta kaksi eniten käytettyä algoritmeja etsimiseen ja lajitteluun ovat lineaarinen haku ja binaarinen haku.
Ero lineaarisen ja binaarisen haun välillä on molempien algoritmien toimivuus ja tehokkuus. Binaarinen haku on paljon tehokkaampi algoritmi verrattuna lineaariseen hakualgoritmiin. Kierto tai aika, joka kuluu kunkin arvon vertailuun ennen lajittelua, on vähemmän binaarisessa haussa verrattuna lineaariseen hakuun.
Lineaarinen haku on erittäin monimutkainen algoritmi, jos haluat etsiä numeroa luettelosta, verrata ja toistaa toisinaan luettelon arvojen lukumäärää. Jokainen luettelon elementti nousee yksitellen ja sitä verrataan viereiseen elementtiin. Kaikkiin elementteihin päästään käsiksi ja tarkistetaan, ja sitten oikea elementti löytyy. Pahimmassa tapauksessa voi olla, jos luettelon viimeinen numero on etsittävä numero. Lineaarinen haku on menetelmä, jolla taulukko kuljetetaan ja etsittävä elementti perustetaan. Jos puhumme tehokkuudesta, tehokkuus on montako kertaa ohjelman on suoritettava löytääkseen numero. Jos löydämme etsimäsi numeron ensimmäisestä sijainnista, on tehtävä vain yksi vertailu, ja asiat lajitellaan, mutta jos ei, vertailut on tehtävä uudestaan ja uudestaan, ja muisti hukkaantuu. Keskimäärin vertailujen lukumäärä on (n + 1/2). Ja tämän tekniikan pahin tapa on, että O (n) tarkoittaa suoritusjärjestystä.
Verrattuna lineaariseen hakuun, binaarihaku on erittäin tehokas. Tässä menetelmässä taulukko jaetaan kahteen osaan ja tällä tavoin vertailujen lukumäärä on hyvin vähemmän verrattuna binaariseen hakuun. Aika on myös vähemmän binaarisessa haussa verrattuna lineaariseen hakuun. Binaarihaku toimii siten, että taulukon keskielementti löydetään ja sitten keskielementtiä verrataan taulukon yhteen osaan. Voi olla kolme vaihtoehtoa, keskimmäinen numero voi olla numero, joka meidän on löydettävä, tai numero, joka on pienempi kuin keskinumero tai luku, joka on suurempi kuin keskimmäisen numeron keskikohta. Vertailujen lukumäärä on korkeintaan log (N + 1). Binaarinen haku verrattuna lineaariseen hakuun on tehokas algoritmi verrattuna lineaariseen hakuun, mutta taulukko on lajiteltava ennen binaarisen haun tekemistä.
Sisältö: Ero lineaarisen ja binaarisen haun välillä
- Vertailutaulukko
- Binaarihaku
- Keskeiset erot
- johtopäätös
- Selittävä video
Vertailutaulukko
| Perusta | Lineaarinen haku | Binaarihaku |
| merkitys | Jokaisen elementin lineaarinen haku tarkistetaan ja verrataan ja lajitellaan sitten | Binaarihaku lajiteltava luettelo on jaettu kahteen osaan ja sitten lajiteltu.
|
| Ajan monimutkaisuus | Lineaarisen haun aikakompleksi on O (N). | Binaarisen haun aikakompleksi on O (loki 2 N) |
| Algoritmin tyyppi | Lineaarinen haku on iteratiivinen. | Binaarihaku on Jaa ja valloita. |
| Koodirivi | Lineaarisessa haussa meidän on kirjoitettava lisää koodia. | Binaarisessa haussa meidän on kirjoitettava vähemmän koodia. |
Lineaarinen haku
Lineaarinen haku on erittäin monimutkainen algoritmi, jos haluat etsiä numeroa luettelosta, verrata ja iteroida joskus luettelon arvojen määrää. Jokainen luettelon elementti nousee yksitellen ja sitä verrataan viereiseen elementtiin. Kaikkiin elementteihin päästään ja ne tarkistetaan, ja sitten oikea elementti löytyy. Pahimmassa tapauksessa voi olla, jos luettelon viimeinen numero on etsittävä numero. Lineaarinen haku on menetelmä, jolla taulukko kuljetetaan ja etsittävä elementti perustetaan. Jos puhumme tehokkuudesta, tehokkuus on montako kertaa ohjelman on suoritettava löytääkseen numero. Jos löydämme etsimäsi numeron ensimmäisestä sijainnista, on tehtävä vain yksi vertailu, ja asiat lajitellaan, mutta jos ei, vertailut on tehtävä uudestaan ja uudestaan, ja muisti hukkaantuu. Keskimäärin vertailujen lukumäärä on (n + 1/2). Ja tämän tekniikan pahin tapa on, että O (n) tarkoittaa suoritusjärjestystä.
Binaarihaku
Verrattuna lineaariseen hakuun, binaarihaku on erittäin tehokas. Tässä menetelmässä taulukko jaetaan kahteen osaan ja tällä tavoin vertailujen lukumäärä on hyvin vähemmän verrattuna binaariseen hakuun. Aika on myös vähemmän binaarisessa haussa verrattuna lineaariseen hakuun. Binaarihaku toimii siten, että taulukon keskielementti löydetään ja sitten keskielementtiä verrataan taulukon yhteen osaan.
Voi olla kolme vaihtoehtoa, keskimmäinen numero voi olla numero, joka meidän on löydettävä, tai numero, joka on pienempi kuin keskinumero tai luku, joka on suurempi kuin keskimmäisen numeron keskikohta. Vertailujen lukumäärä on korkeintaan log (N + 1). Binaarinen haku verrattuna lineaariseen hakuun on tehokas algoritmi verrattuna lineaariseen hakuun, mutta taulukko on lajiteltava ennen binaarisen haun tekemistä.
Keskeiset erot
- Lineaarinen haku jokaista elementtiä tarkistetaan ja verrataan ja lajitellaan, kun taas binaarinen haku lajiteltava luettelo jaetaan kahteen osaan ja lajitellaan sitten.
- Lineaarisen haun aikakompleksisuus on 0 (N), kun taas binaarisen haun aikakompleksisuus on O (log2N).
- Lineaarinen haku on iteratiivinen, kun taas binaarinen haku on Divide and Conquer.
- Lineaarisessa haussa meidän on kirjoitettava enemmän koodia, kun taas binaarisessa haussa meidän on kirjoitettava vähemmän koodia.
johtopäätös
Tässä yllä olevassa artikkelissa näemme selvän eron lineaarisen ja binaarisen haun välillä.
