Vitajte na [www.pocitac.win] Pripojiť k domovskej stránke Obľúbené stránky
1. Lineárne vyhľadávanie (napr. Iterácia prostredníctvom zoznamu alebo poľa):
* Priemerný prípad: O (n/2), ktoré zjednodušujú o (n) . V priemere sa budete musieť pozrieť cez polovicu prvkov.
* Najhorší prípad: O (n) - Kľúčovým slovom je posledný prvok alebo vôbec nie.
* Najlepší prípad: O (1) - Kľúčové slovo je prvým prvkom.
2. Binárne vyhľadávanie (vyžaduje triedenú dátovú štruktúru):
* Priemerný prípad: O (log n)
* Najhorší prípad: O (log n)
* Najlepší prípad: O (1) - Kľúčovým slovom je stredný prvok.
3. Tabuľky hash (alebo mapy hash):
* Priemerný prípad: O (1) - Vynikajúce pre rýchle vyhľadávanie. To predpokladá dobrú hash funkciu, ktorá rovnomerne distribuuje kľúče.
* Najhorší prípad: O (n) - Ak všetky kľúče hash na rovnakom mieste (kolízia), máte efektívne lineárne vyhľadávanie. To je zriedkavé s dobre navrhnutou funkciou hash a faktorom zaťaženia.
* Najlepší prípad: O (1)
4. Stromy (napr. Binárne vyhľadávacie stromy, vyvážené stromy ako AVL alebo červeno-čierne stromy):
* Binárne vyhľadávacie stromy (nevyvážené):
* Priemerný prípad: O (log n) - Ak je strom relatívne vyvážený.
* Najhorší prípad: O (n) - Ak je strom skreslený (ako prepojený zoznam).
* Najlepší prípad: O (1) - Kľúčové slovo je v koreni.
* Vyvážené stromy (avl, červeno-čierne):
* Priemerný prípad: O (log n)
* Najhorší prípad: O (log n) - Zaručte vyváženú štruktúru.
* Najlepší prípad: O (1) - Kľúčové slovo je v koreni.
5. Trie (strom predpony):
* Čas vyhľadávania je úmerný dĺžke kľúčového slova, nie k veľkosti súboru údajov.
* Priemer a najhorší prípad: O (k), kde * k * je dĺžka prehľadávaného kľúčového slova. Pokusy sú veľmi efektívne pre vyhľadávanie založené na predpony a automatické doplnenie.
6. Indexované databázy:
* Výkon sa veľmi spolieha na vytvorené indexy.
* Priemerný prípad: Zvyčajne o (log n) alebo lepšie vďaka štruktúram B B alebo podobným indexovaním.
* Najhorší prípad: Môže sa degradovať na O (n), ak sa index nepoužíva alebo ak dotaz vynúti skenovanie úplného tabuľky.
Súhrnná tabuľka:
| Štruktúra dát/algoritmus Priemerný prípad Najhorší prípad Najlepší prípad Poznámky |
| --------------------------- | -------------- | ------------- | ------------ | ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
| Lineárne vyhľadávanie O (n) | O (n) | O (1) | Jednoduché, ale neefektívne pre veľké súbory údajov. |
| Binárne vyhľadávanie O (log n) | O (log n) | O (1) | Vyžaduje triedené údaje. Veľmi efektívne. |
| Hashova tabuľka O (1) | O (n) | O (1) | V priemere veľmi rýchlo, ale výkon závisí od funkcie hash. Amortizované O (1) na vloženie a vymazanie. |
| Nevyvážený BST O (log n) | O (n) | O (1) | Môže byť efektívny, ale náchylný k najhoršiemu správaniu, ak nie je vyvážený. |
| Balanced BST (AVL, červeno-čierna) O (log n) | O (log n) | O (1) | Zaručený výkon log n. Zložitejšie implementácia ako jednoduchý BST. |
| Trie | O (k) | O (k) | O (1) (prázdne vyhľadávanie reťazcov) | Efektívne pre vyhľadávanie založené na predpony, kde * k * je dĺžka kľúčového slova. |
Kľúčové úvahy o výbere algoritmu:
* veľkosť súboru údajov: V prípade malých súborov údajov nemusí stáť za to režijné náklady zložitejších algoritmov. Lineárne vyhľadávanie môže byť dosť rýchle.
* frekvencia vyhľadávaní: Ak hľadáte často, je rozhodujúca optimalizácia pre výkon vyhľadávania.
* Sú údaje zoradené? Binárne vyhľadávanie vyžaduje zoradené údaje. Ak je potrebné dáta najskôr zoradiť, faktor v čase triedenia.
* Typ vyhľadávania: Je to jednoduché vyhľadávanie kľúčových slov, vyhľadávanie predpony alebo niečo zložitejšie?
* Mentabilita údajov: Ak sa údaje často menia, zvážte náklady na udržiavanie štruktúry údajov (napr. Vyváženie stromu, opätovné vyrovnanie tabuľky hash).
* Použitie pamäte: Niektoré dátové štruktúry (napríklad tabuľky hash) môžu konzumovať významnú pamäť.
Na záver neexistuje jediný „priemerný vyhľadávací runtime“ pre kľúčové slovo. Najlepšia voľba závisí výlučne od kontextu aplikácie a charakteristík údajov. Pre všeobecné vyhľadávanie kľúčových slov vo veľkých súboroch údajov sú tabuľky hash a vyvážené vyhľadávacie stromy bežnou voľbou kvôli ich dobrému výkonu priemerného prípadu. Ak súbor údajov sa často nemení a triedenie je uskutočniteľné, binárne vyhľadávanie poskytuje vynikajúci výkon.