Test maturalny:  Analiza algorytmów

Złożoność czasowa

Asymptotyczna liczba operacji w funkcji rozmiaru danych n.

Oznaczana O(f(n)) — górne ograniczenie.

Złożoność pamięciowa

Asymptotyczne zużycie pamięci dodatkowej w funkcji n.

Stos wywołań rekurencji liczy się do pamięci.

Notacja O()

Górne ograniczenie tempa wzrostu funkcji f(n) dla dużych n.

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)

Niezmiennik pętli

Warunek prawdziwy przed każdą iteracją — narzędzie dowodu poprawności.

Po k krokach bąbelkowego k największych jest na końcu.

Przypadek brzegowy

Skrajna wartość danych wejściowych — n = 0, n = 1, tablica jednoelementowa.

Wykrywa większość błędów off-by-one.

Kontrprzykład

Konkretne wejście, dla którego algorytm zwraca błędny wynik.

Musi spełniać założenia zadania.

Off-by-one

Błąd o jeden — pętla wykonana raz za dużo lub raz za mało.

Sprawdzaj warunki l ≤ p vs l < p.

Śledzenie wykonania

Prowadzenie tabeli stanu zmiennych krok po kroku przez cały algorytm.

Kluczowa technika dla zadań „Analiza algorytmu”.

Złożoność średnia vs najgorsza

Średnia uśrednia po danych losowych; najgorsza dotyczy najbardziej niekorzystnego wejścia.

Quicksort: średnio O(n log n), najgorszy O(n²).

Operacja dominująca

Operacja, której liczba wykonań służy za miarę złożoności algorytmu.

W zadaniu 4 Informatora CKE jest nią przypisanie A[j] ← A[j – 1].

Poprawność algorytmu

Algorytm jest poprawny, gdy dla każdego dopuszczalnego wejścia zwraca oczekiwany wynik.

Dowodzi się przez niezmiennik lub indukcję.

Algorytmy S1 i S2

Oznaczenia dwóch algorytmów w zadaniu 5 Informatora CKE — trzeba rozstrzygnąć, czy każdy z nich sortuje tablicę.

S1 sortuje (to sortowanie przez wstawianie), S2 nie: z [3, 1, 2] daje [1, 3, 2].

1. 1 Zaczynaj od kartki i ołówka: analiza algorytmów to ćwiczenie śledzenia wartości zmiennych krok po kroku.
2. 2 Dla każdego pseudokodu wypisz najpierw rozmiar danych n i zidentyfikuj rzędy zagnieżdżonych pętli — to natychmiast daje O() bez liczenia operacji.
3. 3 Sprawdzaj algorytm na przypadkach brzegowych: jeden element, wszystkie elementy równe, wartości ujemne, duplikaty.
4. 4 W zadaniach z tabelą najpierw wypełnij pola, które wynikają wprost z danych (n, liczba obrotów pętli), a potem trudniejsze.
5. 5 Dla każdego rzędu złożoności zapamiętaj jeden przykład: logarytmiczna — wyszukiwanie binarne, liniowa — wyszukiwanie liniowe, kwadratowa — sortowanie przez wstawianie w przypadku pesymistycznym.
6. 6 Ćwicz porównywanie dwóch algorytmów: zwracaj uwagę nie tylko na liczbę operacji, ale też na pamięć i przypadki brzegowe.
7. 7 Potem przejdź do algorytmów zaawansowanych — ocena złożoności jest tam podstawą.

Powiązane tematy

Te działy łączą się z tematem „Analiza algorytmów” – przećwicz je w Quizie.