Senior
Mis on binaarse otsingu algoritmi keerukus O?
sobes.tech AI
Vastus AI-lt
Binaarse otsingu algoritmi keerukus on O(log n).
Selgitus:
- Binaarne otsing töötab sorteeritud massiivis, iga sammu jooksul jagades otsinguala pooleks.
- Iga sammu jooksul väheneb vaadeldavate elementide arv poole võrra.
- Seetõttu on sammude arv proportsionaalne massiivi suuruse logaritmiga.
Näide: kui massiiv koosneb 1 000 000 elemendist, teeb binaarne otsing umbes 20 võrdlust (log₂(1 000 000) ≈ 20).