Den gennemsnitlige søgningstid for et nøgleord afhænger meget af datastrukturen og algoritmen, der bruges til søgning. Her er en sammenbrud:

1. Lineær søgning (f.eks. Iterering gennem en liste eller array):

* Gennemsnitlig sag: O (n/2) som forenkler til o (n) . I gennemsnit skal du kigge gennem halvdelen af ​​elementerne.

* værste tilfælde: O (n) - Nøgleordet er det sidste element eller overhovedet ikke.

* Bedste tilfælde: O (1) - Nøgleordet er det første element.

2. Binær søgning (kræver en sorteret datastruktur):

* Gennemsnitlig sag: O (log n)

* værste tilfælde: O (log n)

* Bedste tilfælde: O (1) - Nøgleordet er det midterste element.

3. Hash -tabeller (eller hash -kort):

* Gennemsnitlig sag: O (1) - Fremragende til hurtige opslag. Dette antager en god hash -funktion, der distribuerer nøgler jævnt.

* værste tilfælde: O (n) - Hvis alle nøgler hash til det samme sted (en kollision), har du effektivt en lineær søgning. Dette er sjældent med en godt designet hash-funktion og belastningsfaktor.

* Bedste tilfælde: O (1)

4. Træer (f.eks. Binære søgningstræer, afbalancerede træer som AVL eller rød-sorte træer):

* binære søgetræer (ubalanceret):

* Gennemsnitlig sag: O (log n) - Hvis træet er relativt afbalanceret.

* værste tilfælde: O (n) - Hvis træet er skævt (som en tilknyttet liste).

* Bedste tilfælde: O (1) - Nøgleord er roden.

* afbalancerede træer (AVL, rød-sort):

* Gennemsnitlig sag: O (log n)

* værste tilfælde: O (log n) - garanterer en afbalanceret struktur.

* Bedste tilfælde: O (1) - Nøgleord er roden.

5. Trie (præfiks træ):

* Søgningstiden er proportional med længden af ​​nøgleordet, ikke størrelsen på datasættet.

* Gennemsnitlig og værste tilfælde: O (k), hvor * k * er længden af ​​det nøgleord, der søges. Tillinger er meget effektive til præfiksbaserede søgninger og autocomplete.

6. Indekserede databaser:

* Forestillingen er stærkt afhængig af de oprettede indekser.

* Gennemsnitlig sag: Normalt o (log n) eller bedre takket være B-træ eller lignende indekseringsstrukturer.

* værste tilfælde: Kan nedbrydes til O (n), hvis et indeks ikke bruges, eller hvis forespørgslen tvinger en fuld tabel -scanning.

Sammendragstabel:

| Datastruktur/algoritme | Gennemsnitlig sag | Værste tilfælde | Bedste tilfælde | Bemærkninger |

| --------------------------- | -------------- | ------------- | ------------ | -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- |

| Lineær søgning | O (n) | O (n) | O (1) | Enkel, men ineffektiv til store datasæt. |

| Binær søgning | O (log n) | O (log n) | O (1) | Kræver sorterede data. Meget effektiv. |

| Hash -tabel | O (1) | O (n) | O (1) | Meget hurtigt i gennemsnit, men ydeevne afhænger af hash -funktionen. Amortiseret O (1) også til indsættelse og sletning. |

| Ubalanceret BST | O (log n) | O (n) | O (1) | Kan være effektiv, men tilbøjelig til worst-case adfærd, hvis ikke afbalanceret. |

| Afbalanceret BST (AVL, rød-sort) | O (log n) | O (log n) | O (1) | Garanteret log n ydelse. Mere kompleks at implementere end en simpel BST. |

| Trie | O (k) | O (k) | O (1) (tom strengsøgning) | Effektiv til præfiksbaserede søgninger, hvor * k * er længden af ​​nøgleordet. |

Nøgleovervejelser til valg af en algoritme:

* størrelse på datasættet: For små datasæt er overhead af mere komplekse algoritmer muligvis ikke det værd. Lineær søgning kan være hurtig nok.

* Hyppighed af søgninger: Hvis du søger ofte, er det afgørende at optimere efter søgepræstation.

* er dataene sorteret? Binær søgning kræver sorterede data. Hvis dataene først skal sorteres, faktor i sorteringstiden.

* type søgning: Er det et simpelt søgeordsopslag, en præfikssøgning eller noget mere komplekst?

* mutabilitet af dataene: Hvis dataene ofte ændres, skal du overveje omkostningerne ved vedligeholdelse af datastrukturen (f.eks. Ombalancering af et træ, hvilket omvirrer en hash -tabel).

* Hukommelsesbrug: Nogle datastrukturer (som hash -tabeller) kan forbruge betydelig hukommelse.

Afslutningsvis er der ingen enkelt "gennemsnitlig søgningstid" for et nøgleord. Det bedste valg afhænger helt af konteksten af ​​applikationen og egenskaberne ved dataene. For at søge generelle nøgleordssøgning i store datasæt er hashborde og afbalancerede søgningstræer almindelige valg på grund af deres gode gennemsnitlige tilfælde. Hvis datasættet ikke ændrer sig ofte, og sortering er mulig, giver binær søgning fremragende ydelse.