Turinys

• Turinys: skirtumas tarp linijinės ir dvejetainės paieškos
• Palyginimo diagrama
• Dvejetainė paieška
• Pagrindiniai skirtumai
• Išvada
• Aiškinamasis vaizdo įrašas

Skirtumas tarp linijinės ir dvejetainės paieškos yra tas, kad linijinėje paieškoje kiekvienas elementas yra tikrinamas ir lyginamas, o tada rūšiuojamas, tuo tarpu dvejetainėje paieškoje sąrašas, kuris turi būti rūšiuojamas, yra padalintas į dvi dalis ir tada rūšiuojamas. Paieška ir rūšiavimas yra dvi pagrindinės sąvokos kompiuteriniame programavime. Daugybė algoritmų naudojami paieškai ir rūšiavimui, tačiau du dažniausiai naudojami paieškos ir rūšiavimo algoritmai yra linijinė paieška ir dvejetainė paieška.

Skirtumas tarp tiesinės ir dvejetainės paieškos yra abiejų algoritmų veikimas ir efektyvumas. Dvejetainė paieška yra daug efektyvesnis algoritmas, palyginti su linijinės paieškos algoritmu. Kartojimas arba laikas, kurio reikia kiekvienai reikšmei palyginti prieš rūšiavimą, dvejetainėje paieškoje yra mažesnis, palyginti su linijine paieška.

Linijinė paieška yra labai sudėtingas algoritmas, jei norite ieškoti sąraše esančio skaičiaus, palyginti ir kartais pakartoti sąrašo verčių skaičių. Kiekvienas sąrašo elementas po vieną yra gaunamas ir lyginamas su greta esančiu elementu. Visi elementai yra prieinami ir patikrinami, tada randamas tinkamas elementas. Blogiausias atvejis gali būti, jei paskutinis sąrašo numeris yra tas, kurio reikia ieškoti. Linijinė paieška yra metodas, kuriuo masyvas yra apvažiuojamas ir elementas, kurio reikia ieškoti, yra sudarytas. Jei mes kalbame apie efektyvumą, tai efektyvumas yra tai, kiek kartų programa turi būti paleista, norint rasti skaičių. Jei randame skaičių, kurio ieškome pirmoje pozicijoje, reikia atlikti tik vieną palyginimą ir viskas rūšiuojama, tačiau jei ne, vėl ir vėl reikia lyginti, o atmintis eikvojama. Vidutiniškai palyginimų skaičius bus (n + 1/2). O blogiausias šios technologijos veiksmingumas yra tai, kad O (n) reiškia vykdymo tvarką.

Palyginti su linijine paieška, dvejetainė paieška yra labai efektyvi. Šiuo metodu masyvas padalijamas į dvi dalis ir tokiu būdu palyginimų yra labai mažiau, palyginti su dvejetainiu paieška. Dvejetainėje paieškoje laikas taip pat yra mažesnis, palyginti su linijine paieška. Dvejetainė paieška veikia taip, kad randamas vidurinis masyvo elementas, o tada vidurinis elementas lyginamas su viena masyvo dalimi. Gali būti trys galimybės - vidurinis skaičius gali būti skaičius, kurį turime rasti, arba skaičius, mažesnis už vidurinį skaičių, arba skaičius, didesnis už vidurio vidurį. Palyginimų skaičius yra daugiausiai loginis (N + 1). Dvejetainė paieška, palyginti su linijine paieška, yra efektyvus algoritmas, palyginti su linijine paieška, tačiau prieš atliekant dvejetainę paiešką, masyvas turi būti rūšiuojamas.

Turinys: skirtumas tarp linijinės ir dvejetainės paieškos

• Palyginimo diagrama
• Dvejetainė paieška
• Pagrindiniai skirtumai
• Išvada
• Aiškinamasis vaizdo įrašas

Palyginimo diagrama

Linijinė paieška

Linijinė paieška yra labai sudėtingas algoritmas, jei norite ieškoti sąraše esančio skaičiaus, palyginti ir kelis kartus pakartoti sąrašo reikšmių skaičių. Kiekvienas sąrašo elementas po vieną yra gaunamas ir lyginamas su greta esančiu elementu. Visi elementai yra prieinami ir tikrinami, tada randamas tinkamas elementas. Blogiausias atvejis gali būti, jei paskutinis sąrašo numeris yra tas, kurio reikia ieškoti. Linijinė paieška yra metodas, kuriuo masyvas yra apvažiuojamas ir elementas, kurio reikia ieškoti, yra sudarytas. Jei mes kalbame apie efektyvumą, tai efektyvumas yra tai, kiek kartų programa turi būti paleista, norint rasti skaičių. Jei randame skaičių, kurio ieškome pirmoje pozicijoje, reikia atlikti tik vieną palyginimą ir viskas rūšiuojama, tačiau jei ne, vėl ir vėl reikia lyginti, o atmintis eikvojama. Vidutiniškai palyginimų skaičius bus (n + 1/2). O blogiausias šios technikos efektyvumas yra O (n) - vykdymo tvarka.

Dvejetainė paieška

Palyginti su linijine paieška, dvejetainė paieška yra labai efektyvi. Taikant šį metodą, masyvas padalijamas į dvi dalis ir tokiu būdu palyginimų skaičius yra labai mažesnis, palyginti su dvejetainė paieška. Dvejetainėje paieškoje laikas taip pat yra mažesnis, palyginti su linijine paieška. Dvejetainė paieška veikia taip, kad randamas vidurinis masyvo elementas, o tada vidurinis elementas lyginamas su viena masyvo dalimi.

Gali būti trys galimybės - vidurinis skaičius gali būti skaičius, kurį turime rasti, arba skaičius, mažesnis už vidurinį skaičių, arba skaičius, didesnis už vidurio vidurį. Palyginimų skaičius yra daugiausiai loginis (N + 1). Dvejetainė paieška, palyginti su linijine paieška, yra efektyvus algoritmas, palyginti su linijine paieška, tačiau prieš atliekant dvejetainę paiešką, masyvas turi būti rūšiuojamas.

Pagrindiniai skirtumai

1. Linijinė paieška kiekvieno elemento yra tikrinami ir lyginami, o tada rūšiuojami, tuo tarpu dvejetainėje paieškoje sąrašas, kuris turi būti rūšiuojamas, yra padalintas į dvi dalis ir tada rūšiuojamas.
2. Linijinės paieškos laiko sudėtingumas yra 0 (N), tuo tarpu dvejetainės paieškos laiko sudėtingumas yra O (log₂N).
3. Tiesinė paieška kartojasi, tuo tarpu dvejetainė paieška yra „Dalink ir užkariauk“.
4. Linijinėje paieškoje turime parašyti daugiau kodo, tuo tarpu dvejetainėje paieškoje turime parašyti mažiau kodo.

Išvada

Šiame aukščiau esančiame straipsnyje matome aiškų skirtumą tarp linijinės ir dvejetainės paieškos.

Aiškinamasis vaizdo įrašas