Algorytm wyszukiwania elementu w nieposortowanej tablicy jednowymiarowej ma złożoność obliczeniową

Wybierz odpowiedź A stałą, O(1) B silnia, O(n!) C liniową, O(n) D kwadratową, O(n2)

Cały arkusz EE.09, styczeń 2024 Było też: EE.09, styczeń 2025

Pokaż odpowiedź i wyjaśnienie

Poprawna odpowiedź: C

liniową, O(n)

Dlaczego

W nieposortowanej tablicy w najgorszym przypadku trzeba sprawdzić wszystkie n elementów, więc wyszukiwanie liniowe ma złożoność O(n). W tablicy posortowanej wyszukiwanie binarne ma O(log n).