Lineārā meklēšana salīdzinājumā ar bināro meklēšanu
Saturs
- Saturs: atšķirība starp lineāro meklēšanu un bināro meklēšanu
- Salīdzināšanas tabula
- Binārā meklēšana
- Galvenās atšķirības
- Secinājums
- Paskaidrojošs video
Atšķirība starp lineāro meklēšanu un bināro meklēšanu ir tāda, ka lineārajā meklēšanā katrs elements tiek pārbaudīts, salīdzināts un pēc tam sakārtots, turpretī binārā meklēšanā sakārtojamais saraksts tiek sadalīts divās daļās un pēc tam sakārtots. Meklēšana un šķirošana ir divi galvenie jēdzieni datoru programmēšanā. Meklēšanai un šķirošanai tiek izmantoti daudzi algoritmi, bet divi meklēšanai un šķirošanai visbiežāk izmantotie algoritmi ir lineārā meklēšana un binārā meklēšana.
Atšķirība starp lineāro meklēšanu un bināro meklēšanu ir abu algoritmu darbība un efektivitāte. Binārā meklēšana ir daudz efektīvāks algoritms, salīdzinot ar lineārās meklēšanas algoritmu. Ierācija vai laiks, kas nepieciešams katras vērtības salīdzināšanai pirms šķirošanas, binārā meklēšanā ir mazāks nekā lineārajā meklēšanā.
Lineārā meklēšana ir ļoti sarežģīts algoritms, ja vēlaties meklēt numuru sarakstā, salīdzināt un dažreiz atkārtot vērtību vērtību skaitu sarakstā. Katrs saraksta elements tiek iegūts pa vienam un salīdzināts ar blakus esošo elementu. Visiem elementiem piekļūst un tos pārbauda, un tad tiek atrasts pareizais elements. Sliktākajā gadījumā var būt tad, ja pēdējais saraksta numurs ir meklējamais numurs. Lineārā meklēšana ir metode, ar kuras palīdzību tiek veikts masīvs un nodibināts meklējamais elements. Ja mēs runājam par efektivitāti, tad efektivitāte ir reižu skaits, kas programmai jāpalaiž, lai atrastu skaitli. Ja pirmajā pozīcijā atrodam meklēto numuru, tad ir jāveic tikai viens salīdzinājums, un lietas tiek sakārtotas, bet, ja ne, tad salīdzinājumi jāveic atkal un atkal, un atmiņa tiek tērēta. Vidēji salīdzinājumu skaits būs (n + 1/2). Un šīs tehnikas sliktākajā gadījumā efektivitāte ir tāda, ka O (n) apzīmē izpildes kārtību.
Salīdzinājumā ar lineāro meklēšanu binārā meklēšana ir ļoti efektīva. Šajā metodē masīvs ir sadalīts divās daļās, un tādējādi salīdzinājumu skaits ir ļoti mazāks nekā binārā meklēšana. Laiks ir mazāks arī binārajā meklēšanā, salīdzinot ar lineāro meklēšanu. Binārā meklēšana darbojas tādā veidā, ka tiek atrasts masīva vidējais elements un pēc tam vidējais elements tiek salīdzināts ar vienu masīva daļu. Var būt trīs iespējas - vidējais cipars var būt cipars, kas mums jāatrod, vai cipars, kas ir mazāks par vidējo numuru, vai cipars, kas ir lielāks par vidējā cipara vidu. Salīdzinājumu skaits nepārsniedz log (N + 1). Binārā meklēšana salīdzinājumā ar lineāro meklēšanu ir efektīvs algoritms, salīdzinot ar lineāro meklēšanu, taču pirms binārās meklēšanas masīvs ir jāsakārto.
Saturs: atšķirība starp lineāro meklēšanu un bināro meklēšanu
- Salīdzināšanas tabula
- Binārā meklēšana
- Galvenās atšķirības
- Secinājums
- Paskaidrojošs video
Salīdzināšanas tabula
| Pamats | Lineārā meklēšana | Binārā meklēšana |
| Nozīme | Katra elementa lineārā meklēšana tiek pārbaudīta, salīdzināta un pēc tam sakārtota | Binārā meklēšana sakārtojamo sarakstu sadala divās daļās un tad sakārto.
|
| Laika sarežģītība | Lineārās meklēšanas laika sarežģītība ir O (N). | Binārā meklēšanas laika sarežģītība ir O (log 2 N) |
| Algoritma tips | Lineārā meklēšana ir iteratīva. | Binārā meklēšana ir Dalīt un iekarot. |
| Koda rinda | Lineārā meklēšanā mums jāraksta vairāk koda. | Binārā meklēšanā mums ir jāraksta mazāk koda. |
Lineārā meklēšana
Lineārā meklēšana ir ļoti sarežģīts algoritms, ja vēlaties meklēt numuru sarakstā, salīdzināt un dažreiz atkārtot vērtību skaitu sarakstā. Katrs saraksta elements tiek iegūts pa vienam un salīdzināts ar blakus esošo elementu. Visiem elementiem piekļūst un tos pārbauda, un tad tiek atrasts pareizais elements. Sliktākajā gadījumā var būt tad, ja pēdējais saraksta numurs ir meklējamais numurs. Lineārā meklēšana ir metode, ar kuras palīdzību tiek veikts masīvs un nodibināts meklējamais elements. Ja mēs runājam par efektivitāti, tad efektivitāte ir reižu skaits, kas programmai jāpalaiž, lai atrastu skaitli. Ja pirmajā pozīcijā atrodam meklēto numuru, tad ir jāveic tikai viens salīdzinājums, un lietas tiek sakārtotas, bet, ja ne, tad salīdzinājumi jāveic atkal un atkal, un atmiņa tiek tērēta. Vidēji salīdzinājumu skaits būs (n + 1/2). Un šīs tehnikas sliktākajā gadījumā efektivitāte ir tāda, ka O (n) apzīmē izpildes kārtību.
Binārā meklēšana
Salīdzinājumā ar lineāro meklēšanu binārā meklēšana ir ļoti efektīva. Šajā metodē masīvs ir sadalīts divās daļās, un tādējādi salīdzinājumu skaits ir ļoti mazāks nekā binārā meklēšana. Laiks ir mazāks arī binārajā meklēšanā, salīdzinot ar lineāro meklēšanu. Binārā meklēšana darbojas tādā veidā, ka tiek atrasts masīva vidējais elements, un pēc tam vidējais elements tiek salīdzināts ar vienu masīva daļu.
Var būt trīs iespējas - vidējais cipars var būt cipars, kas mums jāatrod, vai cipars, kas ir mazāks par vidējo numuru, vai cipars, kas ir lielāks par vidējā cipara vidu. Salīdzinājumu skaits nepārsniedz log (N + 1). Binārā meklēšana salīdzinājumā ar lineāro meklēšanu ir efektīvs algoritms, salīdzinot ar lineāro meklēšanu, taču pirms binārās meklēšanas masīvs ir jāsakārto.
Galvenās atšķirības
- Katra elementa lineārā meklēšana tiek pārbaudīta, salīdzināta un pēc tam sakārtota, turpretī binārā meklēšana sakārtojamo sarakstu sadala divās daļās un tad sakārto.
- Lineārās meklēšanas laika sarežģītība ir 0 (N), turpretī binārā meklēšanas laika sarežģītība ir O (log2N).
- Lineārā meklēšana ir iteratīva, savukārt binārā meklēšana ir dalāma un iekarojama.
- Lineārajā meklēšanā mums jāraksta vairāk koda, turpretī binārajā meklēšanā mums jāraksta mazāk koda.
Secinājums
Šajā rakstā mēs redzam skaidru atšķirību starp lineāro meklēšanu un bināro meklēšanu.
