Meklēšanas algoritmi ir būtiski datorzinātņu rīki, ko izmanto, lai atrastu konkrētus vienumus datu kolekcijā. Šie algoritmi ir izstrādāti, lai efektīvi pārvietotos pa datu struktūrām, lai atrastu vajadzīgo informāciju, padarot tos par būtiskiem dažādās lietojumprogrammās, piemēram, datu bāzes, tīmekļa meklētājprogrammas , un vēl.
java rakstzīme uz int
Meklēšanas algoritms
Satura rādītājs
- Kas ir Meklēšana?
- Terminu meklēšana
- DMR meklēšanas nozīme
- Meklēšanas lietojumprogrammas
- Meklēšanas algoritmu pamati
- Meklēšanas algoritmi
- Salīdzinājumi starp dažādiem meklēšanas algoritmiem
- Meklēšanas algoritmu realizācijas bibliotēkās
- Vienkāršas problēmas meklēšanā
- Vidējas problēmas meklēšanā
- Sarežģītas problēmas meklēšanā
Kas ir Meklēšana?
Meklēšana ir galvenais process noteikta elementa vai elementa atrašana datu kolekcijā . Šai datu kolekcijai var būt dažādas formas, piemēram, masīvi, saraksti, koki vai citi strukturēti attēlojumi. Meklēšanas galvenais mērķis ir noteikt, vai vēlamais elements pastāv datos, un, ja tā, tad noteikt tā precīzu atrašanās vietu vai izgūt to. Tam ir svarīga loma dažādos skaitļošanas uzdevumos un reālās pasaules lietojumprogrammās, tostarp informācijas izguvē, datu analīzē, lēmumu pieņemšanas procesos un citur.
Meklēšanas terminoloģijas:
Mērķa elements:
Meklējot, datu apkopojumā vienmēr ir kāds konkrēts mērķa elements vai vienums, ko vēlaties atrast. Šis mērķis var būt vērtība, ieraksts, atslēga vai jebkura cita interesējoša datu entītija.
Meklēt vietu:
Meklēšanas laukums attiecas uz visu datu kolekciju, kurā meklējat mērķa elementu. Atkarībā no izmantotās datu struktūras meklēšanas vieta var atšķirties pēc lieluma un organizācijas.
poga centrā CSS
Sarežģītība:
Meklēšana var būt dažāda sarežģītības pakāpe atkarībā no datu struktūras un izmantotā algoritma. Sarežģītību bieži mēra laika un telpas prasību izteiksmē.
Deterministisks pret nedeterministisku:
Daži meklēšanas algoritmi, piemēram binārā meklēšana , ir deterministiski, kas nozīmē, ka tie ievēro skaidru, sistemātisku pieeju. Citi, piemēram, lineārā meklēšana, nav deterministiski, jo tiem, iespējams, būs jāpārbauda visa meklēšanas telpa sliktākajā gadījumā.
lateksa saraksti
DMR meklēšanas nozīme:
- Efektivitāte: Efektīvi meklēšanas algoritmi uzlabo programmas veiktspēju.
- Datu izguve: Ātri atrodiet un izgūstiet konkrētus datus no lielām datu kopām.
- Datu bāzes sistēmas: Ļauj ātri veikt datu bāzu vaicājumus.
- Problēmu risināšana: Izmanto plašā problēmu risināšanas uzdevumu klāstā.
Meklēšanas pielietojumi:
Meklēšanas algoritmiem ir daudz lietojumprogrammu dažādās jomās. Šeit ir dažas izplatītas lietojumprogrammas:
- Informācijas iegūšana: Meklētājprogrammas, piemēram, Google, Bing un Yahoo, izmanto izsmalcinātus meklēšanas algoritmus, lai izgūtu atbilstošu informāciju no milzīga datu apjoma tīmeklī.
- Datu bāzes sistēmas: Meklēšana ir būtiska datu bāzu sistēmās, lai izgūtu konkrētus datu ierakstus, pamatojoties uz lietotāju vaicājumiem, tādējādi uzlabojot datu izguves efektivitāti.
- E-komercija: Meklēšana ir ļoti svarīga e-komercijas platformās, lai lietotāji varētu ātri atrast produktus, pamatojoties uz viņu vēlmēm, specifikācijām vai atslēgvārdiem.
- Tīklošana: Tīklošanā meklēšanas algoritmi tiek izmantoti, lai efektīvi maršrutētu pakešus caur tīkliem, atrastu optimālos ceļus un pārvaldītu tīkla resursus.
- Mākslīgais intelekts: Meklēšanas algoritmiem ir būtiska nozīme AI lietojumprogrammās, piemēram, problēmu risināšanā, spēlēšanā (piem., šahā) un lēmumu pieņemšanas procesos.
- Modeļa atpazīšana: Meklēšanas algoritmi tiek izmantoti modeļu saskaņošanas uzdevumos, piemēram, attēlu atpazīšanā, runas atpazīšanā un rokraksta atpazīšanā.
Meklēšanas algoritmu pamati:
- Ievads meklēšanā – datu struktūras un algoritmu apmācība
- Meklēšanas nozīme datu struktūrā
- Kāds ir meklēšanas algoritma mērķis?
Meklēšanas algoritmi:
- Lineārā meklēšana
- Sentinel lineārā meklēšana
- Binārā meklēšana
- Meta binārā meklēšana | Vienpusēja binārā meklēšana
- Trīskāršā meklēšana
- Pārlēkt meklēšanu
- Interpolācijas meklēšana
- Eksponenciālā meklēšana
- Fibonači meklēšana
- Visuresošā binārā meklēšana
Salīdzinājumi starp dažādiem meklēšanas algoritmiem:
- Lineārā meklēšana pret bināro meklēšanu
- Interpolācijas meklēšana pret bināro meklēšanu
- Kāpēc priekšroka tiek dota binārajai meklēšanai, nevis trīskāršajai meklēšanai?
- Vai Sentinel Lineārā meklēšana ir labāka par parasto Lineāro meklēšanu?
Meklēšanas algoritmu ieviešanas bibliotēkās:
- Binārās meklēšanas funkcijas C++ STL (binārā_meklēšana, apakšējā robeža un augšējā robeža)
- Arrays.binarySearch() Java ar piemēriem | 1. komplekts
- Arrays.binarySearch() Java ar piemēriem | 2. kopa (Meklēt apakšgrupā)
- Collections.binarySearch() Java ar piemēriem
Vienkāršas problēmas meklēšanā:
- Atrodiet trīs lielākos elementus masīvā
- Atrodiet trūkstošo numuru
- Atrodiet pirmo atkārtoto elementu veselu skaitļu masīvā
- Atrodiet trūkstošo un atkārtojošos numuru
- Meklēt, ievietot un dzēst sakārtotā masīvā
- Saskaitiet 1 sakārtotā binārā masīvā
- Divi elementi, kuru summa ir vistuvāk nullei
- Atrodiet pāri ar norādīto atšķirību
- k lielākie (vai mazākie) elementi masīvā
- K. mazākais elements 2D masīvā, kas sakārtots pa rindām un kolonnām
- Atrodiet kopīgus elementus trīs sakārtotos masīvos
- Griesti sakārtotā masīvā
- Stāvs sakārtotā masīvā
- Atrodiet maksimālo elementu masīvā, kas vispirms palielinās un pēc tam samazinās
- Ņemot vērā masīvu ar lielumu n un skaitli k, atrodiet visus elementus, kas parādās vairāk nekā n/k reizes
Vidējas problēmas meklēšanā:
- Atrodiet visus trīskāršus ar nulles summu
- Atrodiet elementu, pirms kura visi elementi ir mazāki par to un pēc kura visi ir lielāki
- Atrodiet lielāko pāru summu nešķirotā masīvā
- K’th mazākais/lielākais elements nešķirotajā masīvā
- Meklēt elementu sakārtotā un pagrieztā masīvā
- Atrodiet minimālo elementu sakārtotā un pagrieztā masīvā
- Atrodiet pīķa elementu
- Masīva maksimālais un minimums, izmantojot minimālo salīdzinājumu skaitu
- Atrodiet fiksēto punktu noteiktā masīvā
- Atrodiet failā k visbiežāk sastopamos vārdus
- Atrodiet k elementi, kas ir vistuvāk dotajai vērtībai
- Dots sakārtots masīvs un skaitlis x, atrodiet masīvā pāri, kura summa ir vistuvāk x
- Atrodiet tuvāko pāri no diviem sakārtotiem masīviem
- Atrodiet trīs tuvākos elementus no dotajiem trīs sakārtotajiem masīviem
- Binārā racionālo skaitļu meklēšana, neizmantojot peldošā komata aritmētiku
Sarežģītas problēmas meklēšanā:
- Divu sakārtotu masīvu mediāna
- Divu sakārtotu dažāda lieluma masīvu mediāna
- Meklēt gandrīz sakārtotā masīvā
- Atrodiet elementa pozīciju sakārtotā bezgalīgu skaitļu masīvā
- Dots sakārtots un pagriezts masīvs, atrodiet, vai ir pāris ar noteiktu summu
- K’th mazākais/lielākais elements nešķirotajā masīvā | Sliktākajā gadījumā lineārais laiks
- K lielākais elements straumē
- Labākā pirmā meklēšana (informēta meklēšana)
Ātrās saites:
- “Prakses problēmas” meklēšanā
- “Viktorīnas” par meklēšanu
Ieteicams:
- Uzziniet datu struktūru un algoritmus | DSA apmācība