Lineárne vyhľadávanie verzus binárne vyhľadávanie
Obsah
- Obsah: Rozdiel medzi lineárnym a binárnym vyhľadávaním
- Porovnávacia tabuľka
- Binárne vyhľadávanie
- Kľúčové rozdiely
- záver
- Vysvetľujúce video
Rozdiel medzi lineárnym vyhľadávaním a binárnym vyhľadávaním spočíva v tom, že pri lineárnom vyhľadávaní sa každý prvok skontroluje a porovná a potom triedi, zatiaľ čo v prípade binárneho vyhľadávania sa zoznam, ktorý sa má triediť, rozdelí na dve časti a potom sa triedi. Vyhľadávanie a triedenie sú dva hlavné pojmy počítačového programovania. Na vyhľadávanie a triedenie sa používa veľa algoritmov, ale dva najpoužívanejšie algoritmy na vyhľadávanie a triedenie sú lineárne a binárne vyhľadávanie.
Rozdiel medzi lineárnym a binárnym vyhľadávaním je funkčnosť a účinnosť oboch algoritmov. Binárne vyhľadávanie je omnoho efektívnejší algoritmus v porovnaní s algoritmom lineárneho vyhľadávania. Iterácia alebo čas potrebný na porovnanie každej hodnoty pred triedením je pri binárnom vyhľadávaní v porovnaní s lineárnym hľadaním menej.
Lineárne vyhľadávanie je veľmi zložitý algoritmus, ak chcete hľadať číslo v zozname, porovnávať a niekedy opakovať počet hodnôt v zozname. Postupne sa vyberie každý prvok zoznamu a porovná sa so susedným prvkom. Prístup ku všetkým prvkom a kontrola a nájdenie správneho prvku. Môže nastať najhorší prípad, ak posledné číslo v zozname je číslo, ktoré sa má prehľadávať. Lineárne vyhľadávanie je metóda, ktorou sa pole prechádza a je založený element, ktorý sa má prehľadávať. Ak hovoríme o efektívnosti, efektívnosť je to, koľkokrát musí program nájsť, aby zistil číslo. Ak nájdeme číslo, ktoré hľadáme, na prvom mieste, potom sa musí urobiť iba jedno porovnanie a veci sa triedia, ale ak nie, potom sa porovnávania musia robiť znova a znova a stráca sa pamäť. Priemerne bude počet porovnaní (n + 1/2). A najhorší prípad účinnosti tejto techniky je O (n), čo znamená poradie vykonania.
V porovnaní s lineárnym vyhľadávaním je binárne vyhľadávanie veľmi efektívne. V tejto metóde je pole rozdelené na dve časti, a tak je počet porovnaní v porovnaní s binárnym vyhľadávaním veľmi menší. Čas je tiež kratší v binárnom vyhľadávaní v porovnaní s lineárnym vyhľadávaním. Binárne vyhľadávanie pracuje tak, že sa nájde stredný prvok poľa a potom sa stredný prvok porovná s jednou časťou poľa. Existujú tri možnosti, ktorými je stredné číslo, môže byť číslo, ktoré musíme nájsť, alebo číslo, ktoré je menšie ako stredné číslo alebo číslo, ktoré je väčšie ako stred stredného čísla. Počet porovnaní je najviac log (N + 1). Binárne vyhľadávanie v porovnaní s lineárnym vyhľadávaním je v porovnaní s lineárnym vyhľadávaním účinným algoritmom, ale pred vykonaním binárneho vyhľadávania je potrebné zoradiť pole.
Obsah: Rozdiel medzi lineárnym a binárnym vyhľadávaním
- Porovnávacia tabuľka
- Binárne vyhľadávanie
- Kľúčové rozdiely
- záver
- Vysvetľujúce video
Porovnávacia tabuľka
| základ | Lineárne vyhľadávanie | Binárne vyhľadávanie |
| zmysel | Lineárne vyhľadávanie je skontrolované a porovnané a potom triedené | Binárne vyhľadávanie zoznam, ktorý sa má triediť, je rozdelený na dve časti a potom triedený.
|
| Časová zložitosť | Časová zložitosť lineárneho vyhľadávania je O (N). | Časová zložitosť binárneho vyhľadávania je O (log 2 N) |
| Typ algoritmu | Lineárne vyhľadávanie je opakujúce sa. | Binárne vyhľadávanie je rozdelenie a dobitie. |
| Riadok kódu | Pri lineárnom vyhľadávaní musíme napísať viac kódu. | Pri binárnom vyhľadávaní musíme napísať menej kódu. |
Lineárne vyhľadávanie
Lineárne vyhľadávanie je veľmi zložitý algoritmus, ak chcete hľadať číslo v zozname, porovnávať a niekoľkokrát opakovať počet hodnôt v zozname. Postupne sa vyberie každý prvok zoznamu a porovná sa so susedným prvkom. Prístup k všetkým prvkom a kontrola a potom nájdenie správneho prvku. Môže nastať najhorší prípad, ak posledné číslo v zozname je číslo, ktoré sa má prehľadávať. Lineárne vyhľadávanie je metóda, ktorou sa pole prechádza a je založený element, ktorý sa má prehľadávať. Ak hovoríme o efektívnosti, efektívnosť je to, koľkokrát musí program nájsť, aby zistil číslo. Ak nájdeme číslo, ktoré hľadáme, na prvom mieste, potom sa musí urobiť iba jedno porovnanie a veci sa triedia, ale ak nie, potom sa porovnávania musia robiť znova a znova a stráca sa pamäť. V priemere bude počet porovnaní (n + 1/2). A najhorší prípad účinnosti tejto techniky je O (n), čo znamená poradie vykonania.
Binárne vyhľadávanie
V porovnaní s lineárnym vyhľadávaním je binárne vyhľadávanie veľmi efektívne. V tejto metóde je pole rozdelené na dve časti, a tak je počet porovnaní v porovnaní s binárnym vyhľadávaním veľmi menší. Čas je tiež kratší v binárnom vyhľadávaní v porovnaní s lineárnym vyhľadávaním. Binárne vyhľadávanie pracuje tak, že sa nájde stredný prvok poľa a potom sa stredný prvok porovná s jednou časťou poľa.
Existujú tri možnosti, ktorými je stredné číslo, môže byť číslo, ktoré musíme nájsť, alebo číslo, ktoré je menšie ako stredné číslo alebo číslo, ktoré je väčšie ako stred stredného čísla. Počet porovnaní je najviac log (N + 1). Binárne vyhľadávanie v porovnaní s lineárnym vyhľadávaním je v porovnaní s lineárnym vyhľadávaním účinným algoritmom, ale pred vykonaním binárneho vyhľadávania je potrebné zoradiť pole.
Kľúčové rozdiely
- Lineárne vyhľadávanie každého prvku je skontrolované a porovnané a potom triedené, zatiaľ čo binárne vyhľadávanie zoznam, ktorý sa má triediť, je rozdelený na dve časti a potom triedený.
- Časová zložitosť lineárneho vyhľadávania je 0 (N), zatiaľ čo časová zložitosť binárneho vyhľadávania je O (log2N).
- Lineárne vyhľadávanie je opakujúce sa, zatiaľ čo binárne vyhľadávanie je rozdelené a podmanené.
- Pri lineárnom vyhľadávaní musíme napísať viac kódu, zatiaľ čo pri binárnom vyhľadávaní musíme napísať menej kódu.
záver
V tomto článku vyššie vidíme jasný rozdiel medzi lineárnym a binárnym vyhľadávaním.
