Algorytmy i struktury danych na egzaminie INF.04

Dla wejścia o rozmiarze n liczy się dominującą liczbę operacji. Stałe i wolniej rosnące składniki pomija się przy opisie rzędu wzrostu, więc 3n + 7 zapisuje się jako O(n), a dwie zagnieżdżone pętle po n elementów zwykle prowadzą do O(n do kwadratu). Złożoność czasowa nie jest czasem w sekundach, tylko sposobem porównania wzrostu kosztu.

Trzeba też uwzględniać pamięć. Sortowanie przez scalanie działa w czasie O(n log n), ale typowa implementacja potrzebuje dodatkowej tablicy O(n). Algorytm może więc być szybszy kosztem pamięci. O(1) pamięci dodatkowej oznacza stałą liczbę zmiennych niezależną od wielkości danych.

W wyszukiwaniu liniowym najlepszy przypadek zachodzi, gdy element jest pierwszy: jedno porównanie, czyli O(1). Najgorszy występuje, gdy element jest ostatni albo go nie ma: n porównań, czyli O(n). Przy jednakowo prawdopodobnych pozycjach średnio potrzeba około połowy listy, ale rząd wzrostu nadal wynosi O(n).

Wyszukiwanie binarne wymaga danych uporządkowanych. Najlepszy przypadek to trafienie w środek w pierwszym kroku, czyli O(1). W przypadku średnim i najgorszym zakres jest dzielony na połowę, więc liczba kroków rośnie jak logarytm i wynosi O(log n). Koszt wcześniejszego sortowania może jednak sprawić, że pojedyncze wyszukanie w nieposortowanej małej tablicy lepiej wykonać liniowo.

Sortowanie bąbelkowe z przerwaniem przy braku zamian ma najlepszy przypadek O(n), a średni i najgorszy O(n do kwadratu). Sortowanie przez wybór wykonuje około n do kwadratu porównań także dla danych już uporządkowanych. Sortowanie przez wstawianie działa w O(n) dla danych uporządkowanych i w O(n do kwadratu) w przypadku średnim oraz najgorszym.

Sortowanie przez scalanie ma O(n log n) w typowych analizach każdego przypadku i wymaga pamięci pomocniczej. Sortowanie szybkie przy w miarę równych podziałach ma O(n log n), lecz przy skrajnie nierównych podziałach może osiągnąć O(n do kwadratu). Stabilność oznacza zachowanie kolejności elementów o równych kluczach. Ma znaczenie na przykład przy kolejnym sortowaniu rekordów wcześniej uporządkowanych po nazwisku.

Tablica daje dostęp po indeksie w O(1), ale wstawienie na początku wymaga przesunięcia elementów. Lista wiązana ułatwia wstawienie przy znanym węźle, lecz dojście do elementu o numerze k jest sekwencyjne. Stos działa według zasady ostatni wszedł, pierwszy wyszedł, a kolejka według zasady pierwszy wszedł, pierwszy wyszedł.

Tablica mieszająca zapewnia oczekiwany dostęp O(1), ale kolizje wymagają obsługi, a w skrajnym przypadku koszt może wzrosnąć do O(n). W zrównoważonym drzewie wyszukiwania odczyt, dodanie i usunięcie mają O(log n), a dane można przejść w kolejności kluczy. Wybór zależy więc od tego, czy ważniejsze są wyszukiwanie, kolejność, częste wstawienia czy zużycie pamięci.

Utwórz tabelę wartości zmiennych i wykonuj instrukcje dokładnie w podanej kolejności. Przy pętli zapisz wartości graniczne i sprawdź, czy koniec przedziału należy do zakresu. Przy rekurencji najpierw znajdź warunek kończący, a potem rozpisz kilka wywołań do momentu powrotu.

Złożoność oceniaj dopiero po ustaleniu liczby powtórzeń. Kolejne pętle sumują koszty, a pętla wewnątrz pętli zwykle je mnoży. Pętla zmniejszająca zakres o jeden daje zwykle O(n), a dzieląca go w każdym kroku przez dwa O(log n). Wyjątki wynikają z pracy wykonywanej wewnątrz, dlatego warto policzyć ją osobno.