Lekcja 12. Analiza algorytmów — kompletny przewodnik maturalny (notacja Big-O)
Trudny / egzaminacyjnyPo co się tego uczymy?
To podsumowanie całego działu Algorytmy i złożoność — narzędzie do FORMALNEJ oceny każdego algorytmu poznanego w poprzednich 11 lekcjach. Na maturze nie wystarczy napisać, że program "działa" — trzeba umieć powiedzieć, JAK DŁUGO będzie działał przy dużych danych i CZY da się to zrobić szybciej. To dokładnie ta umiejętność.
Teoria
Analiza algorytmu to badanie jego: SZYBKOŚCI działania (jak długo trwa wykonanie) i ZAPOTRZEBOWANIA NA PAMIĘĆ (ile danych/zmiennych tworzy). Nie chodzi o mierzenie czasu zegarem, tylko o POLICZENIE, ile kroków (pętli, porównań, operacji) wykona komputer.
Rodzaje analizy:
| Rodzaj analizy | Co sprawdzamy | Przykład |
|---|---|---|
| Czasowa | ile kroków wykona program | BubbleSort vs QuickSort |
| Pamięciowa | ile pamięci zużyje | MergeSort (tablice pomocnicze) |
| Asymptotyczna | jak zachowuje się przy DUŻYCH danych | O(n), O(n log n), O(n²) |
| Przypadków | jak działa w różnych warunkach | QuickSort: best/worst/average |
Notacja Big O — sposób zapisu "jak SZYBKO ROŚNIE liczba operacji" wraz ze wzrostem danych, zamiast konkretnych liczb:
| Notacja | Znaczenie | Przykład |
|---|---|---|
| O(1) | stała liczba kroków | dostęp do elementu listy |
| O(log n) | rośnie wolno | wyszukiwanie binarne |
| O(n) | rośnie liniowo | wyszukiwanie liniowe |
| O(n log n) | prawie liniowy | MergeSort, QuickSort |
| O(n²) | kwadratowy | BubbleSort |
| O(2ⁿ) | wykładniczy | naiwny rekurencyjny Fibonacci |
| O(n!) | silniowy | permutacje — praktycznie nieużywalny |
Przypadki działania (best/average/worst) — każdy algorytm może działać różnie w zależności od danych: best case (najkorzystniejszy, np. Insertion Sort na już posortowanej liście), average case (typowy przypadek, np. QuickSort na losowych danych), worst case (najgorszy możliwy układ, np. QuickSort na już posortowanej liście). Na maturze trzeba umieć podać NAJGORSZY przypadek — to on definiuje teoretyczną złożoność algorytmu.
Podsumowanie złożoności WSZYSTKICH algorytmów z tego działu:
| Algorytm | Czas | Pamięć | Uwagi |
|---|---|---|---|
| Wyszukiwanie liniowe | O(n) | O(1) | najprostsze |
| Wyszukiwanie binarne | O(log n) | O(1) | wymaga sortowania |
| Bubble Sort | O(n²) | O(1) | edukacyjny |
| Insertion Sort | O(n²) / best O(n) | O(1) | dobry dla małych/prawie posortowanych danych |
| Merge Sort | O(n log n) | O(n) | stabilny, zawsze przewidywalny |
| Quick Sort | O(n log n) / worst O(n²) | O(log n) | szybki, ale niestabilny |
| Algorytm Euklidesa | O(log n) | O(1) | klasyczny |
| Szybkie potęgowanie | O(log n) | O(1) | dziel i zwyciężaj |
| BFS / DFS | O(V + E) | O(V) | grafy — V wierzchołków, E krawędzi |
| Dijkstra | O(E log V) | O(V) | tylko wagi dodatnie |
Typowe zadania maturalne — analiza pseudokodu: dla for i in range(n): for j in range(i, n): k += 1 — pętla wewnętrzna wykonuje się n-i razy, sumarycznie 1+2+...+n = n(n+1)/2, czyli O(n²). Dla while n > 0: n = n // 2 — liczba wykonań to log₂ n, czyli O(log n).
Schemat
PORÓWNANIE ZŁOŻONOŚCI (rosnąco): O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!) (stały) (wolny wzrost) (kwadrat) (wykładniczy) (silniowy) Dla listy 10 000 elementów - które sortowanie szybsze? BubbleSort → O(n²) → ~100 000 000 operacji MergeSort → O(n log n)→ ~130 000 operacji Odpowiedź: MergeSort — prawie 800 razy mniej operacji! BEST / AVERAGE / WORST CASE (QuickSort): Best/Average: O(n log n) - pivot dzieli dane w miarę równo Worst: O(n²) - pivot zawsze skrajny (np. dane już posortowane)
Przykład z życia
Aplikacja bankowa sortująca listę milionów transakcji MUSI używać algorytmu o złożoności O(n log n) (jak MergeSort), a nie O(n²) (jak BubbleSort) — różnica między kilkoma sekundami a kilkoma GODZINAMI przetwarzania. To właśnie analiza złożoności decyduje, który algorytm trafia do prawdziwego, produkcyjnego kodu.
insertion_sort.py
# Sortowanie przez wstawianie (Insertion Sort) - nowy algorytm w tym podsumowaniu
# Każdy element trafia w odpowiednie miejsce w już posortowanej części listy
def insertion_sort(tab):
for i in range(1, len(tab)):
klucz = tab[i]
j = i - 1
while j >= 0 and tab[j] > klucz:
tab[j + 1] = tab[j]
j -= 1
tab[j + 1] = klucz
return tab
# Analiza: czas O(n^2), ale best case O(n) gdy dane prawie posortowane
# Pamięć: O(1) - sortuje "na miejscu"
print(insertion_sort([5, 2, 8, 1, 9]))quick_sort.py
# QuickSort - kolejny algorytm "dziel i zwyciężaj", ale z inną strategią niż MergeSort
def quick_sort(tab):
if len(tab) <= 1:
return tab
pivot = tab[0] # wybierz element "oś"
mniejsze = [x for x in tab[1:] if x <= pivot] # wszystko mniejsze/równe pivotowi
wieksze = [x for x in tab[1:] if x > pivot] # wszystko większe od pivota
return quick_sort(mniejsze) + [pivot] + quick_sort(wieksze)
# Analiza: średnio O(n log n), najgorzej O(n^2) - gdy pivot źle dzieli dane
# (np. gdy lista jest już posortowana, a pivot to zawsze pierwszy element)
print(quick_sort([5, 2, 8, 1, 9]))Komentarz i wyjaśnienie kodu
W insertion_sort() pętla wewnętrzna while j >= 0 and tab[j] > klucz przesuwa elementy WIĘKSZE od aktualnie wstawianego w prawo, robiąc miejsce dla klucz — to jak sortowanie kart w ręku, wsuwając każdą nową kartę na właściwe miejsce między już poukładanymi.
W quick_sort() zwróć uwagę, DLACZEGO może działać wolno: jeśli pivot (zawsze PIERWSZY element listy) trafia na listę JUŻ POSORTOWANĄ, to mniejsze będzie ZAWSZE puste, a wieksze będzie miało prawie WSZYSTKIE pozostałe elementy — algorytm zamiast dzielić dane na pół (jak przy dobrym wyborze pivota), dzieli je na "0 i reszta", co daje O(n²) zamiast O(n log n). To dokładnie pytanie maturalne z teorii tej lekcji.
Ćwiczenie samodzielne
Uruchom insertion_sort() i quick_sort() dla tej samej listy i porównaj wyniki. Następnie uruchom quick_sort() na liście, która jest JUŻ POSORTOWANA (np. [1,2,3,4,5]) i zastanów się, ile porównań wykona w tym najgorszym przypadku.
Zadania do pracy własnej
Dla poniższego pseudokodu określ złożoność obliczeniową:
for i in range(n): print(i)orazfor i in range(n): for j in range(n): print(i, j). Uzasadnij odpowiedź, licząc liczbę wykonań instrukcjiprint.Dla listy 10 000 elementów oblicz w przybliżeniu, ile operacji wykona: (a) wyszukiwanie liniowe w najgorszym przypadku, (b) wyszukiwanie binarne w najgorszym przypadku, (c) BubbleSort, (d) MergeSort. Przedstaw wyniki w tabeli i skomentuj różnice rzędów wielkości.
Napisz program mierzący RZECZYWISTY czas wykonania (moduł
time) dla: BubbleSort, InsertionSort, MergeSort i QuickSort na tej samej losowej liście o rosnącej wielkości (100, 1000, 10 000 elementów). Narysuj (na kartce lub w arkuszu kalkulacyjnym) wykres czasu w zależności od n dla każdego algorytmu i sprawdź, czy kształt wykresów odpowiada teoretycznej złożoności (n² dla Bubble/Insertion, n log n dla Merge/Quick).
Typowe błędy
Podawanie AVERAGE CASE zamiast WORST CASE jako "złożoności algorytmu" — na maturze pytanie o złożoność algorytmu domyślnie dotyczy NAJGORSZEGO przypadku (worst case), chyba że pytanie wyraźnie precyzuje inaczej (np. dla QuickSort trzeba umieć podać OBA: średnio O(n log n), najgorzej O(n²)).
Mylenie złożoności CZASOWEJ z PAMIĘCIOWĄ — algorytm może być szybki czasowo (np. MergeSort, O(n log n)), ale zużywać więcej pamięci (O(n), bo tworzy dodatkowe tablice) niż algorytm wolniejszy czasowo, ale oszczędniejszy pamięciowo (np. BubbleSort, O(1) pamięci).
Zakładanie, że "szybszy w praktyce" zawsze znaczy "lepsza złożoność teoretyczna" — dla MAŁYCH zbiorów danych (kilkanaście elementów) prostszy algorytm (np. Insertion Sort) może być w praktyce szybszy niż teoretycznie "lepszy" MergeSort, ze względu na mniejszy narzut (overhead) na tworzenie dodatkowych struktur.
Nawiązanie do egzaminu zawodowego
To podsumowanie CAŁEGO działu "Algorytmy i złożoność" — każdy z 11 poprzednich tematów (Euklides i Sito, wyszukiwanie binarne, sortowania, bisekcja, szybkie potęgowanie, rekurencja, podejście zachłanne, programowanie dynamiczne, stos/kolejka, lider, grafy) można teraz opisać formalnym językiem złożoności obliczeniowej — dokładnie tak, jak wymaga tego pisemna część matury rozszerzonej z informatyki. Umiejętność analizy złożoności to też fundament dla działu Python — programowanie (poprzedni dział tej ścieżki), gdzie te same algorytmy są implementowane praktycznie.