Kwalifikacja: INF.03 - Tworzenie i administrowanie stronami i aplikacjami internetowymi oraz bazami danych
Zawód: Technik informatyk , Technik programista
Kategorie: Programowanie webowe Algorytmy i podstawy informatyki
Jaką złożoność obliczeniową ma algorytm wyszukiwania elementu w nieposortowanej tablicy jednowymiarowej?
Odpowiedzi
Dobrze. W nieposortowanej tablicy w najgorszym razie sprawdza się wszystkie n elementów.
Źle. Kwadratowa złożoność dotyczy np. zagnieżdżonych pętli, nie pojedynczego przejścia po tablicy.
Źle. Złożoność silni rośnie skrajnie szybko - dotyczy np. permutacji, nie wyszukiwania.
Źle. Stała złożoność oznacza dostęp niezależny od rozmiaru, np. po indeksie - tu trzeba przeglądać elementy.
Informacja zwrotna
W nieposortowanej tablicy nie ma porządku, który pozwoliłby pominąć część elementów, więc element szuka się przeglądając kolejne pozycje (wyszukiwanie liniowe). W najgorszym przypadku trzeba sprawdzić wszystkie n elementów, dlatego złożoność wynosi O(n) - liniowa. Dlatego poprawna jest złożoność liniowa, O(n).