Analiza algorytmów – kompletny przewodnik maturalny

1. Co to jest analiza algorytmu

Każdy algorytm da się wykonać, ale nie każdy robi to równie dobrze.
Dwa programy mogą dawać ten sam wynik, lecz jeden wykona się w sekundę, a drugi w godzinę.
Analiza algorytmu pozwala zrozumieć, dlaczego tak się dzieje.

Analiza algorytmu to badanie jego:

szybkości działania – czyli jak długo trwa wykonanie programu,
zapotrzebowania na pamięć – ile danych i zmiennych tworzy w trakcie działania.

Nie chodzi o to, by mierzyć czas zegarem, ale policzyć, ile kroków (pętli, porównań, operacji) wykona komputer.

2. Dlaczego ją wykonujemy

Na maturze z informatyki nie wystarczy napisać, że coś „działa”.
Trzeba też wiedzieć:

jak długo będzie działać przy dużych danych,
czy zajmie dużo pamięci,
czy da się to zrobić szybciej.

To właśnie analiza algorytmiczna — nauka myślenia, jak komputer.

3. Jak analizujemy algorytmy

Każdy algorytm można zbadać na kilka sposobów:

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

4. Notacja Big O – prostym językiem

Notacja Big O (duże O) to sposób zapisu „jak szybko rośnie liczba operacji”.
Zamiast mówić: „program robi 30 porównań dla 10 elementów, a 3000 dla 100”,
mówimy po prostu: O(n²) – czyli rosnący kwadratowo z ilością danych.

Notacja	Znaczenie	Przykład	Komentarz
O(1)	stała liczba kroków	dostęp do elementu listy	zawsze tak samo szybki
O(log n)	rośnie wolno	wyszukiwanie binarne	dzieli dane na pół
O(n)	rośnie liniowo	wyszukiwanie liniowe	jedno przejście
O(n log n)	prawie liniowy	MergeSort, QuickSort	szybkie sortowanie
O(n²)	kwadratowy	BubbleSort	dwie pętle
O(2ⁿ)	wykładniczy	rekurencyjny Fibonacci	bardzo wolny
O(n!)	silniowy	permutacje	praktycznie nieużywalny

5. Przypadki działania (best, average, worst)

Każdy algorytm może działać różnie w zależności od danych:

Przypadek	Co oznacza	Przykład
Best case	najkorzystniejszy – dane prawie gotowe	Insertion Sort na posortowanej liście
Average case	typowy przypadek	QuickSort na losowych danych
Worst case	najgorszy możliwy układ danych	QuickSort na już posortowanej liście

Na maturze trzeba umieć podać najgorszy przypadek, bo to on definiuje teoretyczną złożoność.

6. Analiza algorytmów – konkretne przykłady

Każdy opis zawiera:

krótki pomysł działania,
przykład kodu w Pythonie,
analizę czasową i pamięciową,
przykładowe pytanie maturalne z uzasadnieniem.

6.1 Wyszukiwanie

A) Liniowe wyszukiwanie

Najprostsza metoda – przeglądasz element po elemencie, aż znajdziesz ten, którego szukasz.

def wyszukiwanie_liniowe(lista, x):
    for i in lista:
        if i == x:
            return True
    return False

def wyszukiwanie_liniowe(lista, x):
    for i in lista:
        if i == x:
            return True
    return False

Analiza:

Czas: O(n) – w najgorszym przypadku trzeba sprawdzić wszystkie elementy.
Pamięć: O(1) – tylko zmienna pomocnicza.

Uzasadnienie:
Dla listy 10 000 elementów komputer musi wykonać maks. 10 000 porównań.

Matura:

Ile porównań wykona program w najgorszym przypadku?
Odpowiedź: n (czyli tyle, ile elementów ma lista).

B) Wyszukiwanie binarne

Działa tylko na posortowanej liście.
Przy każdym kroku sprawdza środek i odrzuca połowę danych.

def wyszukiwanie_binarne(lista, x):
    lewy, prawy = 0, len(lista) - 1
    while lewy <= prawy:
        s = (lewy + prawy) // 2
        if lista[s] == x:
            return s
        elif lista[s] < x:
            lewy = s + 1
        else:
            prawy = s - 1
    return -1

def wyszukiwanie_binarne(lista, x):
    lewy, prawy = 0, len(lista) - 1
    while lewy <= prawy:
        s = (lewy + prawy) // 2
        if lista[s] == x:
            return s
        elif lista[s] < x:
            lewy = s + 1
        else:
            prawy = s - 1
    return -1

Analiza:

Czas: O(log n) – za każdym razem połowa danych znika.
Pamięć: O(1).

Uzasadnienie:
Dla 1024 elementów → log₂(1024) = 10 porównań.

Matura:

Ile maksymalnie porównań wykona ten algorytm dla 1024 elementów?
Odpowiedź: 10.

6.2 Sortowanie

A) Sortowanie bąbelkowe

Porównuje sąsiednie elementy i zamienia, jeśli są w złej kolejności.

def bubble_sort(tab):
    for i in range(len(tab)-1):
        for j in range(len(tab)-i-1):
            if tab[j] > tab[j+1]:
                tab[j], tab[j+1] = tab[j+1], tab[j]
    return tab

def bubble_sort(tab):
    for i in range(len(tab)-1):
        for j in range(len(tab)-i-1):
            if tab[j] > tab[j+1]:
                tab[j], tab[j+1] = tab[j+1], tab[j]
    return tab

Analiza:

Czas: O(n²) – dwie zagnieżdżone pętle.
Pamięć: O(1) – sortuje „na miejscu”.
Best: O(n), gdy dane prawie posortowane.
Worst: O(n²), gdy odwrotnie posortowane.

Uzasadnienie:
Dla n=5 porównań: 4+3+2+1=10 → rośnie proporcjonalnie do n².

Matura:

Ile porównań wykona BubbleSort dla listy 100 elementów?
Odpowiedź: około 100² = 10 000.

B) Sortowanie przez wstawianie

Każdy element trafia w odpowiednie miejsce w rosnącej 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

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²), best O(n)
Pamięć: O(1)
Działa szybciej, gdy dane są prawie posortowane.

C) Sortowanie przez scalanie (MergeSort)

def merge_sort(tab):
    if len(tab) <= 1:
        return tab
    s = len(tab)//2
    lewa = merge_sort(tab[:s])
    prawa = merge_sort(tab[s:])
    return scal(lewa, prawa)

def scal(lewa, prawa):
    wynik, i, j = [], 0, 0
    while i < len(lewa) and j < len(prawa):
        if lewa[i] < prawa[j]:
            wynik.append(lewa[i]); i += 1
        else:
            wynik.append(prawa[j]); j += 1
    return wynik + lewa[i:] + prawa[j:]

def merge_sort(tab):
    if len(tab) <= 1:
        return tab
    s = len(tab)//2
    lewa = merge_sort(tab[:s])
    prawa = merge_sort(tab[s:])
    return scal(lewa, prawa)

def scal(lewa, prawa):
    wynik, i, j = [], 0, 0
    while i < len(lewa) and j < len(prawa):
        if lewa[i] < prawa[j]:
            wynik.append(lewa[i]); i += 1
        else:
            wynik.append(prawa[j]); j += 1
    return wynik + lewa[i:] + prawa[j:]

Analiza:

Czas: O(n log n)
Pamięć: O(n) (tworzy nowe listy)
Stabilny, zawsze przewidywalny.

Uzasadnienie:
Każdy poziom dzieli listę na pół → log n poziomów,
a scalanie każdego poziomu wymaga przejścia przez n elementów.
Czyli n * log n operacji.

D) QuickSort

def quick_sort(tab):
    if len(tab) <= 1:
        return tab
    pivot = tab[0]
    mniejsze = [x for x in tab[1:] if x <= pivot]
    wieksze = [x for x in tab[1:] if x > pivot]
    return quick_sort(mniejsze) + [pivot] + quick_sort(wieksze)

def quick_sort(tab):
    if len(tab) <= 1:
        return tab
    pivot = tab[0]
    mniejsze = [x for x in tab[1:] if x <= pivot]
    wieksze = [x for x in tab[1:] if x > pivot]
    return quick_sort(mniejsze) + [pivot] + quick_sort(wieksze)

Analiza:

Średnio: O(n log n)
Najgorzej: O(n²), gdy pivot zawsze skrajny
Pamięć: O(log n)

Matura:

Dlaczego QuickSort może działać wolniej od MergeSort?
Bo gdy pivot źle dzieli dane (np. lista już posortowana),
każda część ma prawie pełną długość, więc złożoność staje się kwadratowa.

6.3 Algorytmy numeryczne

A) Algorytm Euklidesa (NWD)

def nwd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

def nwd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

Analiza:

Czas: O(log n)
Pamięć: O(1)
Bardzo wydajny nawet dla dużych liczb.

B) Szybkie potęgowanie

def fast_pow(a, n):
    wynik = 1
    while n > 0:
        if n % 2 == 1:
            wynik *= a
        a *= a
        n //= 2
    return wynik

def fast_pow(a, n):
    wynik = 1
    while n > 0:
        if n % 2 == 1:
            wynik *= a
        a *= a
        n //= 2
    return wynik

Analiza:

Czas: O(log n)
Pamięć: O(1)
Uzasadnienie: przy każdym kroku wykładnik dzielimy na pół.

C) Metoda połowienia (bisekcji)

def bisekcja(f, a, b, eps):
    while abs(b - a) > eps:
        s = (a + b) / 2
        if f(a) * f(s) < 0:
            b = s
        else:
            a = s
    return (a + b) / 2

def bisekcja(f, a, b, eps):
    while abs(b - a) > eps:
        s = (a + b) / 2
        if f(a) * f(s) < 0:
            b = s
        else:
            a = s
    return (a + b) / 2

Analiza:

Czas: O(log((b−a)/ε))
Pamięć: O(1)
Każdy krok dzieli przedział przez 2.

6.4 Rekurencja i strategie

Rekurencja

def silnia(n):
    if n == 0:
        return 1
    return n * silnia(n - 1)

def silnia(n):
    if n == 0:
        return 1
    return n * silnia(n - 1)

Analiza:

Czas: O(n)
Pamięć: O(n) (stos wywołań)
Ryzyko: przepełnienie stosu dla dużych n.

Uzasadnienie:
Każde wywołanie funkcji czeka na poprzednie – tworzy się „łańcuch zależności”.

Podejście zachłanne

Wybierasz najlepsze rozwiązanie na każdym etapie – nie zawsze optymalne globalnie.

def wydaj_reszte(kwota, monety):
    wynik = []
    for m in monety:
        while kwota >= m:
            kwota -= m
            wynik.append(m)
    return wynik

print(wydaj_reszte(83, [50, 20, 10, 2, 1]))

def wydaj_reszte(kwota, monety):
    wynik = []
    for m in monety:
        while kwota >= m:
            kwota -= m
            wynik.append(m)
    return wynik

print(wydaj_reszte(83, [50, 20, 10, 2, 1]))

Analiza:

Czas: O(n)
Pamięć: O(1)
Działa poprawnie, jeśli monety mają strukturę zachłanną (np. w złotówkach).

6.5 Algorytmy grafowe

BFS (wszerz)

from collections import deque

def bfs(graf, start):
    odw = set()
    q = deque([start])
    while q:
        v = q.popleft()
        if v not in odw:
            odw.add(v)
            q.extend(graf[v])
    return odw

from collections import deque

def bfs(graf, start):
    odw = set()
    q = deque([start])
    while q:
        v = q.popleft()
        if v not in odw:
            odw.add(v)
            q.extend(graf[v])
    return odw

Analiza:

Czas: O(V + E)
Pamięć: O(V)
Najkrótsze ścieżki w grafie bez wag.

DFS (w głąb)

def dfs(graf, start, odw=None):
    if odw is None:
        odw = set()
    odw.add(start)
    for s in graf[start]:
        if s not in odw:
            dfs(graf, s, odw)
    return odw

def dfs(graf, start, odw=None):
    if odw is None:
        odw = set()
    odw.add(start)
    for s in graf[start]:
        if s not in odw:
            dfs(graf, s, odw)
    return odw

Analiza:

Czas: O(V + E)
Pamięć: O(V) (rekurencja)

Dijkstra

import heapq

def dijkstra(graf, start):
    dist = {v: float('inf') for v in graf}
    dist[start] = 0
    q = [(0, start)]
    while q:
        d, v = heapq.heappop(q)
        if d > dist[v]:
            continue
        for sasiad, koszt in graf[v]:
            nowy = d + koszt
            if nowy < dist[sasiad]:
                dist[sasiad] = nowy
                heapq.heappush(q, (nowy, sasiad))
    return dist

import heapq

def dijkstra(graf, start):
    dist = {v: float('inf') for v in graf}
    dist[start] = 0
    q = [(0, start)]
    while q:
        d, v = heapq.heappop(q)
        if d > dist[v]:
            continue
        for sasiad, koszt in graf[v]:
            nowy = d + koszt
            if nowy < dist[sasiad]:
                dist[sasiad] = nowy
                heapq.heappush(q, (nowy, sasiad))
    return dist

Analiza:

Czas: O(E log V)
Pamięć: O(V)
Nie działa dla ujemnych wag.

7. Typowe zadania maturalne

Określ złożoność algorytmu w pseudokodzie: for i in range(n): for j in range(i, n): k += 1 Rozwiązanie:
Pętla wewnętrzna wykonuje się n−i razy → 1 + 2 + … + n = n(n+1)/2 → O(n²).
Dla kodu: while n > 0: n = n // 2 Złożoność: log₂ n → O(log n).
Dla listy 10 000 elementów – który algorytm szybciej posortuje dane?
- BubbleSort → O(n²) → 100 mln operacji,
- MergeSort → O(n log n) → ~130 000 operacji.
  Odpowiedź: MergeSort.

8. Podsumowanie

Algorytm	Czas	Pamięć	Uwagi
Wyszukiwanie liniowe	O(n)	O(1)	najprostsze
Wyszukiwanie binarne	O(log n)	O(1)	wymaga sortu
Bubble Sort	O(n²)	O(1)	edukacyjny
Insertion Sort	O(n²)/O(n)	O(1)	dobry dla małych danych
MergeSort	O(n log n)	O(n)	stabilny
QuickSort	O(n log n)/O(n²)	O(log n)	szybki, niestabilny
Euklides	O(log n)	O(1)	klasyczny
Fast pow	O(log n)	O(1)	dziel i zwyciężaj
BFS/DFS	O(V+E)	O(V)	grafy
Dijkstra	O(E log V)	O(V)	wagi dodatnie

9. Wniosek końcowy

Analiza algorytmu to nie tylko teoria – to sposób myślenia o programie.
Uczeń, który rozumie, dlaczego coś działa szybko lub wolno,
potrafi sam znaleźć lepsze rozwiązanie na maturze i w życiu.