Lineární vyhledávání vs. binární vyhledávání
Obsah
- Obsah: Rozdíl mezi lineárním a binárním vyhledáváním
- Srovnávací tabulka
- Binární vyhledávání
- Klíčové rozdíly
- Závěr
- Vysvětlující video
Rozdíl mezi lineárním vyhledáváním a binárním vyhledáváním spočívá v tom, že v lineárním vyhledávání je každý prvek zkontrolován a porovnán a poté tříděn, zatímco v binárním vyhledávání je seznam, který má být tříděn, rozdělen do dvou částí a poté tříděn. Vyhledávání a třídění jsou dva hlavní pojmy v počítačovém programování. Mnoho algoritmů se používá pro vyhledávání a třídění, ale dva nejpoužívanější algoritmy pro vyhledávání a třídění jsou lineární a binární vyhledávání.
Rozdíl mezi lineárním a binárním vyhledáváním spočívá v práci a účinnosti obou algoritmů. Binární vyhledávání je mnohem efektivnější algoritmus ve srovnání s algoritmem lineárního vyhledávání. Iterace nebo doba potřebná k porovnání každé hodnoty před tříděním je v binárním vyhledávání méně ve srovnání s lineárním vyhledáváním.
Lineární vyhledávání je velmi složitý algoritmus, pokud chcete hledat číslo v seznamu, porovnávat a někdy iterovat počet hodnot v seznamu. Každý prvek seznamu se postupně získává a porovnává se sousedním prvkem. Všechny prvky jsou zpřístupněny a zkontrolovány a poté je nalezen správný prvek. Může být nejhorší případ, pokud poslední číslo v seznamu je číslo, které má být prohledáno. Lineární vyhledávání je metoda, kterou je pole procházeno a element, který má být prohledáván, je založen. Pokud mluvíme o účinnosti, je to účinnost, kolikrát musí program najít, aby našel číslo. Pokud najdeme číslo, které hledáme na první pozici, pak se musí provést pouze jedno srovnání a věci se třídí, ale pokud ne, pak se musí porovnávání provádět znovu a znovu a ztrácí se paměť. V průměru bude počet srovnání (n + 1/2). A nejhorší případová účinnost této techniky je O (n) znamená pořadí provedení.
Ve srovnání s lineárním vyhledáváním je binární vyhledávání velmi efektivní. V této metodě je pole rozděleno na dvě části, a tak je počet srovnání ve srovnání s binárním vyhledáváním velmi menší. Čas je také kratší v binárním vyhledávání ve srovnání s lineárním vyhledáváním. Binární vyhledávání pracuje tak, že je nalezen střední prvek pole a poté je střední prvek porovnán s jednou částí pole. Existují tři možnosti, kterými jsou střední číslo, může být číslo, které musíme najít, nebo číslo, které je menší než střední číslo nebo číslo, které je větší než střed středního čísla. Počet srovnání je nanejvýš log (N + 1). Binární vyhledávání ve srovnání s lineárním vyhledáváním je účinný algoritmus ve srovnání s lineárním vyhledáváním, ale pole musí být před provedením binárního vyhledávání tříděno.
Obsah: Rozdíl mezi lineárním a binárním vyhledáváním
- Srovnávací tabulka
- Binární vyhledávání
- Klíčové rozdíly
- Závěr
- Vysvětlující video
Srovnávací tabulka
| Základ | Lineární vyhledávání | Binární vyhledávání |
| Význam | Lineární vyhledávání každého prvku je zkontrolováno a porovnáno a poté tříděno | Binární vyhledávání seznam, který má být tříděn, je rozdělen na dvě části a poté tříděn.
|
| Časová složitost | Časová složitost lineárního vyhledávání je O (N). | Časová složitost binárního vyhledávání je O (log 2 N) |
| Typ algoritmu | Lineární vyhledávání je iterativní. | Binární vyhledávání je Rozdělit a dobýt. |
| Řádek kódu | Při lineárním vyhledávání musíme napsat více kódu. | Při binárním hledání musíme napsat méně kódu. |
Lineární vyhledávání
Lineární vyhledávání je velmi složitý algoritmus, pokud chcete hledat číslo v seznamu, porovnat a několikrát iterovat počet hodnot v seznamu. Každý prvek seznamu se postupně získává a porovnává se sousedním prvkem. Všechny prvky jsou zpřístupněny a zkontrolovány a poté je nalezen správný prvek. Může být nejhorší případ, pokud poslední číslo v seznamu je číslo, které má být prohledáno. Lineární vyhledávání je metoda, kterou je pole procházeno a element, který má být prohledáván, je založen. Pokud mluvíme o účinnosti, je to účinnost, kolikrát musí program najít, aby našel číslo. Pokud najdeme číslo, které hledáme na první pozici, pak se musí provést pouze jedno srovnání a věci se třídí, ale pokud ne, pak se musí porovnávání provádět znovu a znovu a ztrácí se paměť. V průměru bude počet srovnání (n + 1/2). A nejhorším případem účinnosti této techniky je O (n) znamená pořadí provedení.
Binární vyhledávání
Ve srovnání s lineárním vyhledáváním je binární vyhledávání velmi efektivní. V této metodě je pole rozděleno na dvě části, a tak je počet srovnání ve srovnání s binárním vyhledáváním velmi menší. Čas je také kratší v binárním vyhledávání ve srovnání s lineárním vyhledáváním. Binární vyhledávání pracuje tak, že je nalezen střední prvek pole a poté je střední prvek porovnán s jednou částí pole.
Existují tři možnosti, kterými jsou střední číslo, může být číslo, které musíme najít, nebo číslo, které je menší než střední číslo nebo číslo, které je větší než střed středního čísla. Počet srovnání je nanejvýš log (N + 1). Binární vyhledávání ve srovnání s lineárním vyhledáváním je účinný algoritmus ve srovnání s lineárním vyhledáváním, ale pole musí být před provedením binárního vyhledávání tříděno.
Klíčové rozdíly
- Lineární vyhledávání každého prvku je zkontrolováno a porovnáno a poté tříděno, zatímco binární vyhledávání seznam, který má být tříděn, je rozdělen na dvě části a poté tříděn.
- Časová složitost lineárního vyhledávání je 0 (N), zatímco časová složitost binárního vyhledávání je O (log2N).
- Lineární vyhledávání je iterativní, zatímco binární vyhledávání je dělení a dobytí.
- Při lineárním vyhledávání potřebujeme napsat více kódu, zatímco v binárním vyhledávání musíme napsat méně kódu.
Závěr
V tomto článku výše vidíme jasný rozdíl mezi lineárním a binárním vyhledáváním.
