Wyszukiwanie elementu w nieposortowanej tablicy jednowymiarowej najczęściej realizuje się jako wyszukiwanie liniowe (sekwencyjne): porównujemy szukany klucz z kolejnymi elementami tablicy, idąc od początku do końca.
W takiej sytuacji liczba wykonanych porównań zależy od tego, gdzie znajduje się szukany element (albo czy w ogóle istnieje):
- najgorszy przypadek: element jest na końcu albo go nie ma – wykonujemy około n porównań, czyli O(n);
- średni przypadek: statystycznie również proporcjonalnie do n, więc nadal O(n);
- najlepszy przypadek: element jest na pierwszej pozycji – wtedy może wyjść O(1), ale to nie opisuje typowej gwarancji dla nieposortowanych danych.
Dlatego odpowiedź "liniową, O(n)" jest właściwa jako standardowa charakterystyka kosztu wyszukiwania w nieposortowanej tablicy.
Pozostałe odpowiedzi są błędne, bo:
- "stałą, O(1)" dotyczy tylko najlepszego przypadku (trafienie od razu) albo innych struktur danych (np. tablic haszujących w sprzyjających założeniach), a nie ogólnego wyszukiwania w nieposortowanej tablicy;
- "kwadratową, O(n2)" pojawia się zwykle przy zagnieżdżonych pętlach (np. porównywanie każdej pary elementów), a nie przy pojedynczym przejściu po tablicy;
- "silnia, O(n!)" jest typowa dla algorytmów przeglądu wszystkich permutacji (np. brutalne rozwiązania niektórych problemów kombinatorycznych) i nie ma związku z prostym wyszukiwaniem jednego elementu.
Wskazówka egzaminacyjna: gdy widzisz "nieposortowana tablica" i "szukamy elementu", domyślnie myśl o jednym przejściu pętlą po danych (jedna pętla) → O(n). Gdy pojawiają się dwie pętle zagnieżdżone → często O(n2).
