Cerca lineal i cerca binària
Content
- Contingut: diferència entre la cerca lineal i la cerca binària
- Gràfic de comparació
- Cerca binària
- Diferències claus
- Conclusió
- Vídeo explicatiu
La diferència entre la cerca lineal i la cerca binària és que a la cerca lineal cada element es comprova i es compara i s’ordena, mentre que a la cerca binària es divideix una llista que es divideix en dues parts i després s’ordena. Cercar i ordenar són dos conceptes principals en la programació d’ordinadors. S'utilitzen molts algorismes per cercar i ordenar, però els dos algorismes més utilitzats per cercar i ordenar són la cerca lineal i la cerca binària.
La diferència entre la cerca lineal i la cerca binària és el funcionament i l’eficàcia d’ambdós algoritmes. La cerca binària és un algorisme molt més eficient en comparació amb l'algorisme de cerca lineal. La iteració o el temps que es triga a comparar cada valor abans d’ordenar és menor en la cerca binària en comparació amb la cerca lineal.
La cerca lineal és un algorisme molt complex si voleu cercar un número en una llista, comparar i iterar de vegades el nombre de valors de la llista. Un a un cada element de la llista es recupera i es compara amb l’element adjacent. S'accedeix i comprova tots els elements i es troba l'element correcte. Pot haver el pitjor dels casos si l'últim número de la llista és el que s'ha de cercar. La cerca lineal és el mètode pel qual es travessa la matriu i es funda l’element que s’ha de cercar. Si parlem d’eficiència, l’eficiència és la quantitat de vegades que el programa s’ha d’executar per trobar el número. Si trobem el número que busquem a la primera posició, només s’ha de fer una comparació, i les coses s’ordenen, però si no, les comparacions s’han de fer una i altra vegada, i la memòria es malgasta. El nombre de comparacions serà, de mitjana, (n + 1/2). I la pitjor eficiència d’aquesta tècnica és que O (n) és l’ordre d’execució.
En comparació amb la cerca lineal, la cerca binària és molt eficient. En aquest mètode, la matriu es divideix en dues parts i d'aquesta manera el nombre de comparacions és molt menor en comparació amb la cerca binària. El temps també és menor en la cerca binària en comparació amb la cerca lineal. La cerca binària funciona de manera que es troba l’element mig de la matriu i, a continuació, es compara l’element mig amb una part de la matriu. Hi pot haver tres possibilitats que siguin el nombre mig que pugui ser el nombre que necessitem trobar o el nombre que sigui inferior al número mitjà o el nombre més gran que el del mig. El nombre de comparacions és, com a màxim, log (N + 1). La cerca binària en comparació amb la cerca lineal és un algorisme eficient en comparació amb la cerca lineal, però la matriu s'ha d'ordenar abans de fer la cerca binària.
Contingut: diferència entre la cerca lineal i la cerca binària
- Gràfic de comparació
- Cerca binària
- Diferències claus
- Conclusió
- Vídeo explicatiu
Gràfic de comparació
| Bases | Cerca lineal | Cerca binària |
| Significat | Cerca lineal cada element es comprova i es compara i es ordena després | La cerca binària una llista que s'ha d'ordenar es divideix en dues parts i després s'ordena.
|
| Complexitat horària | La complexitat temporal de la cerca lineal és O (N). | La complexitat horària de la cerca binària és O (log 2 N) |
| Tipus d'algoritme | La cerca lineal és iterativa. | La cerca binària és Dividir i conquerir. |
| Línia de codi | En una cerca lineal, hem d’escriure més codi. | En una cerca binària, hem d’escriure menys codi. |
Cerca lineal
La cerca lineal és un algorisme molt complex si voleu cercar un número en una llista, comparar i repetir algunes vegades el nombre de valors de la llista. Un a un cada element de la llista es recupera i es compara amb l’element adjacent. S'hi accedeix i es comprova tots els elements i es troba l'element correcte. Pot haver el pitjor dels casos si l'últim número de la llista és el que s'ha de cercar. La cerca lineal és el mètode pel qual es travessa la matriu i es funda l’element que s’ha de cercar. Si parlem d’eficiència, l’eficiència és la quantitat de vegades que el programa s’ha d’executar per trobar el número. Si trobem el número que busquem a la primera posició, només s’ha de fer una comparació, i les coses s’ordenen, però si no, les comparacions s’han de fer una i altra vegada, i la memòria es malgasta. En mitjana, el nombre de comparacions serà (n + 1/2). I la pitjor eficiència dels casos d’aquesta tècnica és que O (n) significa l’ordre d’execució.
Cerca binària
En comparació amb la cerca lineal, la cerca binària és molt eficient. En aquest mètode, la matriu es divideix en dues parts i d'aquesta manera el nombre de comparacions és molt menor en comparació amb la cerca binària. El temps també és menor en la cerca binària en comparació amb la cerca lineal. La cerca binària funciona de manera que es troba l’element mig de la matriu i, a continuació, es compara l’element mig amb una part de la matriu.
Hi pot haver tres possibilitats que siguin el nombre mig que pugui ser el nombre que necessitem trobar o el nombre que sigui inferior al número mitjà o el nombre més gran que el del mig. El nombre de comparacions és, com a màxim, log (N + 1). La cerca binària en comparació amb la cerca lineal és un algorisme eficient en comparació amb la cerca lineal, però la matriu s'ha d'ordenar abans de fer la cerca binària.
Diferències claus
- Cerca lineal cada element es comprova i es compara i es ordena, mentre que la cerca binària una llista que s'ha d'ordenar es divideix en dues parts i després s'ordena.
- La complexitat horària de la cerca lineal és 0 (N) mentre que la complexitat horària de la cerca binària és O (log2N).
- La cerca lineal és iterativa mentre que la cerca binària és Dividir i conquerir.
- En la cerca lineal, hem d’escriure més codi mentre que en la cerca binària hem d’escriure menys codi.
Conclusió
En aquest article anterior veiem la clara diferència entre la cerca lineal i la cerca binària.
