Paieškos algoritmai yra pagrindiniai kompiuterių mokslo įrankiai, naudojami konkrečių elementų vietai duomenų rinkinyje rasti. Šie algoritmai skirti efektyviai naršyti duomenų struktūras ir rasti reikiamą informaciją, todėl jie yra esminiai įvairiose programose, pvz. duomenų bazės, interneto paieškos sistemos , ir dar.
Paieškos algoritmas
Java burbulų rūšiavimas
Turinys
- Kas yra Ieškoti?
- Terminologijos paieška
- Paieškos DSA svarba
- Paieškos programos
- Paieškos algoritmų pagrindai
- Paieškos algoritmai
- Įvairių paieškos algoritmų palyginimai
- Bibliotekų paieškos algoritmų įgyvendinimai
- Lengvos problemos ieškant
- Vidutinės problemos ieškant
- Sunkios problemos ieškant
Kas yra Ieškoti?
Paieška yra pagrindinis procesas konkretaus elemento ar elemento radimas duomenų rinkinyje . Šis duomenų rinkinys gali būti įvairių formų, pavyzdžiui, masyvų, sąrašų, medžių ar kitų struktūrinių vaizdų. Pagrindinis paieškos tikslas yra nustatyti, ar norimas elementas yra duomenyse, ir, jei taip, nustatyti tikslią jo vietą arba jį gauti. Jis atlieka svarbų vaidmenį atliekant įvairias skaičiavimo užduotis ir realaus pasaulio programas, įskaitant informacijos gavimą, duomenų analizę, sprendimų priėmimo procesus ir kt.
Paieškos terminai:
Tikslinis elementas:
Ieškant duomenų rinkinyje visada yra konkretus tikslinis elementas arba elementas, kurį norite rasti. Šis tikslas gali būti vertė, įrašas, raktas arba bet koks kitas dominantis duomenų objektas.
Ieškoti erdvėje:
Paieškos erdvė reiškia visą duomenų rinkinį, kuriame ieškote tikslinio elemento. Atsižvelgiant į naudojamą duomenų struktūrą, paieškos erdvė gali skirtis pagal dydį ir organizavimą.
Sudėtingumas:
Atsižvelgiant į duomenų struktūrą ir naudojamą algoritmą, paieška gali būti įvairaus sudėtingumo. Sudėtingumas dažnai matuojamas laiko ir erdvės reikalavimais.
np.log
Deterministinis ir nedeterministinis:
Kai kurie paieškos algoritmai, pvz dvejetainė paieška , yra deterministiniai, tai reiškia, kad jie laikosi aiškaus, sistemingo požiūrio. Kiti, pavyzdžiui, linijinė paieška, yra nedeterministiniai, nes jiems blogiausiu atveju gali tekti ištirti visą paieškos erdvę.
Paieškos DSA svarba:
- Efektyvumas: Veiksmingi paieškos algoritmai pagerina programos našumą.
- Duomenų gavimas: Greitai raskite ir gaukite konkrečius duomenis iš didelių duomenų rinkinių.
- Duomenų bazių sistemos: Įgalina greitą duomenų bazių užklausą.
- Problemų sprendimas: Naudojamas atliekant daugybę problemų sprendimo užduočių.
Paieškos programos:
Paieškos algoritmai turi daugybę pritaikymų įvairiose srityse. Štai keletas įprastų programų:
- Informacijos gavimas: Paieškos sistemos, tokios kaip Google, Bing ir Yahoo, naudoja sudėtingus paieškos algoritmus, kad gautų reikiamą informaciją iš didžiulio duomenų kiekio žiniatinklyje.
- Duomenų bazių sistemos: Duomenų bazių sistemose paieška yra labai svarbi norint gauti konkrečius duomenų įrašus pagal vartotojų užklausas ir pagerinti duomenų gavimo efektyvumą.
- Elektroninė prekyba: El. prekybos platformose paieška yra labai svarbi, kad vartotojai galėtų greitai rasti produktus pagal savo pageidavimus, specifikacijas ar raktinius žodžius.
- Tinklas: Kuriant tinklus, paieškos algoritmai naudojami efektyviam paketų nukreipimui per tinklus, optimalių kelių paieškai ir tinklo išteklių valdymui.
- Dirbtinis intelektas: Paieškos algoritmai atlieka gyvybiškai svarbų vaidmenį AI programose, tokiose kaip problemų sprendimas, žaidimai (pvz., šachmatai) ir sprendimų priėmimo procesai.
- Rašto atpažinimas: Paieškos algoritmai naudojami atliekant šablonų derinimo užduotis, tokias kaip vaizdo atpažinimas, kalbos atpažinimas ir rašysenos atpažinimas.
Paieškos algoritmų pagrindai:
- Paieškos įvadas – duomenų struktūros ir algoritmų pamoka
- Paieškos duomenų struktūroje svarba
- Koks yra paieškos algoritmo tikslas?
Paieškos algoritmai:
- Linijinė paieška
- Sentinel linijinė paieška
- Dvejetainė paieška
- Meta dvejetainė paieška | Vienpusė dvejetainė paieška
- Trinarė paieška
- Peršokti paieška
- Interpoliacijos paieška
- Eksponentinė paieška
- Fibonačio paieška
- Visur esanti dvejetainė paieška
Įvairių paieškos algoritmų palyginimai:
- Linijinė paieška vs dvejetainė paieška
- Interpoliacinė paieška vs dvejetainė paieška
- Kodėl dvejetainei paieškai teikiama pirmenybė, o ne trinarė paieška?
- Ar „Sentinel Linear Search“ yra geresnė nei įprasta linijinė paieška?
Paieškos algoritmų įgyvendinimas bibliotekoje:
- Dvejetainės paieškos funkcijos C++ STL (dvejetainė paieška, apatinė_riba ir viršutinė_riba)
- Arrays.binarySearch() Java su pavyzdžiais | 1 rinkinys
- Arrays.binarySearch() Java su pavyzdžiais | 2 rinkinys (Ieškoti pogrupyje)
- Collections.binarySearch() Java su pavyzdžiais
Lengvos problemos ieškant:
- Raskite tris didžiausius masyvo elementus
- Raskite trūkstamą numerį
- Raskite pirmąjį pasikartojantį sveikųjų skaičių masyvo elementą
- Raskite trūkstamą ir pasikartojantį skaičių
- Ieškokite, įterpkite ir ištrinkite surūšiuotame masyve
- Suskaičiuokite 1 surūšiuotame dvejetainiame masyve
- Du elementai, kurių suma artimiausia nuliui
- Raskite porą su nurodytu skirtumu
- k didžiausių (arba mažiausių) masyvo elementų
- K-tas mažiausias elementas rūšiuotame 2D masyve pagal eilutes ir stulpelius
- Raskite bendrus elementus trijuose surūšiuotuose masyvuose
- Lubos surūšiuotame masyve
- Grindys surūšiuotame masyve
- Raskite didžiausią masyvo elementą, kuris pirmiausia didėja, o paskui mažėja
- Atsižvelgdami į n dydžio masyvą ir skaičių k, raskite visus elementus, kurie pasirodo daugiau nei n/k kartų
Vidutinės problemos ieškant:
- Raskite visus trynukus su nuline suma
- Raskite elementą, prieš kurį visi elementai yra mažesni už jį, o po kurio visi yra didesni
- Raskite didžiausią poros sumą nerūšiuotame masyve
- K'th mažiausias / didžiausias nerūšiuoto masyvo elementas
- Ieškokite elemento surūšiuotame ir pasuktame masyve
- Raskite minimalų elementą surūšiuotame ir pasuktame masyve
- Raskite smailės elementą
- Maksimalus ir minimumas masyve naudojant mažiausią palyginimų skaičių
- Raskite fiksuotą tašką duotame masyve
- Raskite k dažniausiai pasitaikančius žodžius iš failo
- Raskite k elementų, artimiausių nurodytai reikšmei
- Duotas surūšiuotas masyvas ir skaičius x, masyve raskite porą, kurios suma artimiausia x
- Raskite artimiausią porą iš dviejų surūšiuotų masyvų
- Raskite tris artimiausius elementus iš trijų surūšiuotų masyvų
- Dvejetainė racionaliųjų skaičių paieška nenaudojant slankiojo kablelio aritmetikos
Sunkios problemos ieškant:
- Dviejų surūšiuotų masyvų mediana
- Dviejų skirtingų dydžių surūšiuotų masyvų mediana
- Ieškokite beveik surūšiuotame masyve
- Raskite elemento vietą surūšiuotame begalinių skaičių masyve
- Duotas surūšiuotas ir pasuktas masyvas, suraskite, ar yra pora su nurodyta suma
- K'th mažiausias / didžiausias nerūšiuoto masyvo elementas | Blogiausiu atveju tiesinis laikas
- K-as pagal dydį srauto elementas
- Geriausia pirmoji paieška (informuota paieška)
Greitos nuorodos:
- „Praktikos problemos“ ieškant
- „Viktorinos“ apie paiešką
Rekomenduojamas:
- Sužinokite duomenų struktūrą ir algoritmus | DSA mokymo programa