Dział II

Analiza Algorytmów na Suchej Kartce (Dry Run)

Jak czytać pseudokod CKE? Tworzenie tabelek śledzenia zmiennych, rozrysowywanie drzew rekurencji oraz szacowanie złożoności obliczeniowej Big O.

Wstęp: Bądź jak kompilator

Zadania z analizy algorytmów bezlitośnie weryfikują, czy potrafisz "myśleć jak procesor". Komputer masz na sali przez cały egzamin, ale w tych zadaniach dostajesz surowy pseudokod i pytanie: "Co wypisze ten algorytm dla n = 5?". Metoda "na oko" zazwyczaj kończy się błędem o jedną iterację (tzw. błąd off-by-one). W tym dziale nauczysz się niezawodnych technik śledzenia algorytmów: od tabelek zmiennych, przez drzewa wywołań, aż po błyskawiczne szacowanie złożoności.

📋 Spis treści

Iteracja (Pętle)

1 Tabelka śledzenia zmiennych (Dry Run)
2 Pętle zagnieżdżone

Rekurencja i Złożoność

3 Magia Rekurencji: Drzewa wywołań
4 Złożoność obliczeniowa (Notacja Big O)
5 Rekurencja z dwoma wywołaniami
6 Dokładna liczba operacji
7 Pięć pułapek przy śledzeniu

Tabelka śledzenia zmiennych (Dry Run)

To najprostsza, a zarazem najbardziej skuteczna metoda ratująca punkty na maturze. Zamiast zgadywać wynik, rysujesz na brudnopisie tabelkę, gdzie każda kolumna to jedna zmienna z algorytmu, a każdy wiersz to jeden pełny obrót pętli.

Przykład: Pętla dopóki (while)

Przeanalizuj poniższy pseudokod:

a ← 2
b ← 5
dopóki b > 0 wykonuj:
a ← a + 2
b ← b - 2
wypisz a, b

Tworzymy tabelkę śledzenia:

Iteracja	a	b	Warunek b > 0
Start (0)	2	5	5 > 0 (Prawda)
1	4	3	3 > 0 (Prawda)
2	6	1	1 > 0 (Prawda)
3	8	-1	-1 > 0 (Fałsz)

Wniosek: Pętla przerwie się, gdy $b = -1$ . Algorytm wypisze liczby: 8, -1.

Pętle zagnieżdżone (Pętla w pętli)

To najczęstsze źródło błędów w zadaniach CKE. Gdy mamy zewnętrzną pętlę ze zmienną $i$ i wewnętrzną ze zmienną $j$ , musisz pamiętać, że wewnętrzna pętla musi wykonać się w całości, zanim zewnętrzna pętla przejdzie do kolejnego kroku!

🧠

Złota Zasada Zagnieżdżeń

Jeśli zewnętrzna pętla kręci się $N$ razy, a wewnętrzna $M$ razy, to instrukcje ukryte w samym środku wykonają się dokładnie $N \cdot M$ razy.

s ← 0
dla i = 1 do 3 wykonuj:
dla j = 1 do 2 wykonuj:
s ← s + i + j

Zewnętrzna robi 3 kroki (i=1, 2, 3). Wewnętrzna robi 2 kroki (j=1, 2). Zatem zmienna $s$ zostanie zwiększona 6 razy. Nie zgaduj wyników – rozpisuj krok po kroku!

Magia Rekurencji: Drzewa wywołań

Rekurencja (funkcja wywołująca samą siebie) potrafi przepalić zwoje mózgowe, jeśli próbujesz ją śledzić w pamięci. Zamiast tabelki, do rekurencji zawsze rysuj drzewo wywołań (call tree).

Przykład: Własna funkcja rekurencyjna

Zadanie: Co zwróci wywołanie F(3) dla poniższej funkcji?

funkcja F(n):
    jeśli n == 0 to:
        zwróć 1
    w przeciwnym razie:
        zwróć F(n - 1) + 2

Krok 1. Zejście w dół (Rozwijanie wywołań):

F(3) czeka na zwrot z → F(2) + 2

F(2) czeka na zwrot z → F(1) + 2

F(1) czeka na zwrot z → F(0) + 2

F(0) uderza w warunek bazowy! Zwraca → 1

Krok 2. Powrót (Zwijanie wywołań - Backtracking):

Skoro F(0) = 1, to F(1) = 1 + 2 = 3

Skoro F(1) = 3, to F(2) = 3 + 2 = 5

Skoro F(2) = 5, to F(3) = 5 + 2 = 7

Zawsze najpierw zejdź na samo dno (do warunku stopu), a dopiero potem dodawaj/mnoż wartości, wracając do góry.

Złożoność obliczeniowa (Notacja Big O)

Złożoność odpowiada na pytanie: "Jeśli ilość danych wzrośnie dwukrotnie, o ile dłużej będzie działał ten algorytm?". CKE nie wymaga od Ciebie precyzyjnych dowodów matematycznych, musisz jednak umieć poprawnie sklasyfikować algorytm do odpowiedniego rzędu.

\mathcal{O}(1)

Stała

Czas wykonania jest zawsze taki sam, niezależnie od wielkości danych $n$ . Np. odczyt pierwszego elementu z tablicy lub proste równanie matematyczne.

\mathcal{O}(\log n)

Logarytmiczna

Z każdym krokiem pętli zbiór danych zmniejsza się o połowę (lub inną stałą część). Klasyczny przykład to Wyszukiwanie Binarne. Bardzo szybka!

\mathcal{O}(n)

Liniowa

Czas rośnie proporcjonalnie do danych. Występuje, gdy używasz jednej standardowej pętli (np. wyszukiwanie liniowe min/max w nieposortowanej tablicy).

\mathcal{O}(n^2)

Kwadratowa

Niebezpieczna przy dużych plikach. Oznacza zagnieżdżoną pętlę (pętla w pętli). Spotykana np. w standardowym Sortowaniu Bąbelkowym.

\mathcal{O}(n \log n)

Liniowo-logarytmiczna

Rząd dobrych algorytmów sortowania: przez scalanie i szybkiego (średnio). W praktyce niewiele wolniejsza od liniowej, a nieporównywalnie szybsza od kwadratowej — to właśnie ta różnica decyduje przy pliku z milionem liczb.

\mathcal{O}(2^n)

Wykładnicza

Każdy krok podwaja pracę. Tak zachowuje się rekurencja z dwoma wywołaniami, na przykład naiwny ciąg Fibonacciego, oraz przeglądanie wszystkich podzbiorów. Przy $n = 50$ nie doczekasz wyniku.

Ile to naprawdę kroków

n	log n	n	n log n	n²
1 000	10	1 000	10 000	1 000 000
1 000 000	20	1 000 000	20 000 000	10¹²

Ta tabelka tłumaczy, dlaczego przy plikach z arkusza maturalnego (dziesiątki tysięcy wierszy) algorytm kwadratowy potrafi się nie doczekać końca, a liniowo-logarytmiczny kończy natychmiast. Jeśli w zadaniu programistycznym twój kod „wisi”, pierwsze pytanie brzmi: czy nie mam tu pętli w pętli.

Trik CKE na szacowanie złożoności: Zignoruj operacje poza pętlami. Zlicz, ile razy wykona się "najgłębsza" pętla.

1 pętla przechodząca po tablicy N-elementowej = $\mathcal{O}(n)$
2 zagnieżdżone pętle (od 1 do N każda) = $\mathcal{O}(n^2)$
Pętla while, która w każdym kroku dzieli n przez 2 = $\mathcal{O}(\log n)$

Rekurencja z dwoma wywołaniami

Funkcja $F(n-1) + 2$ z poprzedniej sekcji wywołuje samą siebie raz — jej śledzenie to prosty łańcuszek. Gdy w treści pojawiają się dwa wywołania, jak w ciągu Fibonacciego, łańcuszek zamienia się w drzewo i liczba wywołań wybucha. To ulubione zadanie CKE, bo sprawdza jednocześnie śledzenie i rozumienie złożoności.

Klasyczna definicja rekurencyjna:

funkcja Fib(n):
    jeśli n < 2 to:
        zwróć n
    zwróć Fib(n-1) + Fib(n-2)

Warunek stopu obsługuje dwa przypadki naraz: $n = 0$ i $n = 1$ . Gdyby sprawdzał tylko $n = 0$ , wywołanie $Fib(1)$ zeszłoby do $Fib(-1)$ i algorytm nigdy by się nie zatrzymał. To najczęstszy błąd w zadaniach „popraw algorytm”.

Drzewo wywołań dla Fib(4):

Fib(4)
├── Fib(3)
│   ├── Fib(2)
│   │   ├── Fib(1) = 1
│   │   └── Fib(0) = 0
│   └── Fib(1) = 1
└── Fib(2)
  ├── Fib(1) = 1
  └── Fib(0) = 0

Dziewięć wywołań na policzenie $Fib(4) = 3$ . Zwróć uwagę, że Fib(2) liczy się dwa razy, a Fib(1) aż trzy — to właśnie powtarzanie tej samej pracy daje złożoność $\mathcal{O}(2^n)$ .

⚡

Jak to naprawić na egzaminie

Gdy zadanie mówi „policz dla n = 60”, wersja rekurencyjna nie ma szans. Masz dwa wyjścia, oba akceptowane przez CKE:

1. Zamień na iterację. Dwie zmienne pomocnicze i jedna pętla dają złożoność

\mathcal{O}(n)

— to najprostsze i najpewniejsze rozwiązanie.

2. Zapamiętuj wyniki (spamiętywanie). Trzymaj policzone wartości w tablicy albo słowniku i sprawdzaj, zanim policzysz ponownie. Też schodzi do

\mathcal{O}(n)

, a zachowuje rekurencyjny zapis.

Warto też wiedzieć, dlaczego zbyt głęboka rekurencja kończy się komunikatem o błędzie: każde wywołanie zajmuje miejsce na stosie wywołań, a ten ma ograniczony rozmiar. W Pythonie domyślny limit to około tysiąca zagnieżdżeń.

Gdy CKE pyta o dokładną liczbę operacji

Notacja $\mathcal{O}$ wystarcza do pytania „jak szybko rośnie”, ale arkusze potrafią zapytać wprost: „ile porównań wykona algorytm dla tablicy 10-elementowej”. Wtedy trzeba policzyć dokładnie, a nie z dokładnością do rzędu.

Wyszukiwanie liniowe — najgorszy przypadek $n$ porównań, średnio około $n/2$ , najlepszy 1 (element na początku).
Wyszukiwanie binarne — najwyżej $\lceil \log_2 n \rceil$ porównań: dla 1000 elementów 10, dla miliona 20. Wymaga posortowanej tablicy i to trzeba w odpowiedzi napisać.
Znalezienie maksimum — dokładnie $n - 1$ porównań, bo pierwszy element przyjmujesz jako wzorzec.
Znalezienie maksimum i minimum naraz — naiwnie $2n - 2$ , ale porównując elementy parami schodzisz do około $1{,}5n$ . Typowe pytanie „czy da się szybciej”.
Sortowanie bąbelkowe — pełna wersja robi $\frac{n(n-1)}{2}$ porównań, czyli 45 dla dziesięciu elementów. Wersja z flagą kończy wcześniej, gdy tablica jest już posortowana.

Liczby pierwsze — pytanie, które wraca co roku. Sprawdzanie podzielności przez wszystkie liczby od 2 do $n-1$ to $\mathcal{O}(n)$ . Wystarczy jednak sprawdzić dzielniki do $\sqrt{n}$ , bo gdyby istniał dzielnik większy, jego para byłaby mniejsza i już by się znalazła. To skraca pracę z tysiąca kroków do trzydziestu dwóch i jest jedną z najczęściej punktowanych obserwacji w części teoretycznej.

Pięć pułapek przy śledzeniu

Zakres pętli. W pseudokodzie CKE zapis dla i = 1 do n obejmuje również wartość $n$ , czyli $n$ obrotów. W Pythonie range(1, n) kończy się na $n-1$ . Przepisując algorytm z arkusza do kodu, to jest pierwsze miejsce, które się psuje.
Moment sprawdzania warunku. Pętla dopóki sprawdza warunek przed wykonaniem instrukcji, więc może nie wykonać się ani razu. Pętla powtarzaj … aż wykona się co najmniej raz.
Wypisanie w pętli czy po pętli. Wcięcie decyduje o tym, czy zobaczysz jedną liczbę, czy całą serię. W pseudokodzie CKE wcięcie jest jedynym znacznikiem bloku — czytaj je tak uważnie jak treść.
Dzielenie całkowite. Zapis $n \div 2$ albo div obcina część ułamkową: 7 div 2 to 3, nie 3,5. Przy wyszukiwaniu binarnym i konwersji na system dwójkowy pomyłka tutaj zmienia cały wynik.
Kolejność podstawień przy zamianie. Zamiana wartości dwóch zmiennych wymaga trzeciej zmiennej pomocniczej. Zapis $a \leftarrow b$ , a potem $b \leftarrow a$ daje dwie takie same wartości — to klasyczne zadanie „wskaż błąd w algorytmie”.

Przetestuj swoje zwoje mózgowe!

Śledzenie kodu to czysta praktyka. Przejdź do naszej bazy quizów i spróbuj odgadnąć, jaki wynik zwrócą algorytmy przygotowane na wzór zeszłorocznych arkuszy maturalnych CKE.

Rozwiąż Quiz z Analizy Algorytmów 🚀

Przeczytaj też

Informatyka czy fizyka na rozszerzeniu?

Porównanie obu egzaminów: forma, materiał, czas przygotowania i test decyzyjny na dziesięć pytań.

Korepetycje z informatyki

Zdajesz maturę rozszerzoną z informatyki?

Prowadzimy indywidualne przygotowanie do matury z informatyki — algorytmy, Python i C++, bazy danych i arkusz kalkulacyjny. Zajęcia online, na arkuszach CKE. Zobacz program i cennik.

Zobacz korepetycje z informatyki

Uczysz się w technikum informatycznym? Prowadzimy też przygotowanie do kwalifikacji INF.02, INF.03 i INF.04. Zobacz egzaminy zawodowe →

← Poprzedni DziałSystemy Liczbowe i Reprezentacja Danych Następny Dział →Architektura Komputerów i Systemy Operacyjne

Teoria opanowana? Czas na sprawdzenie wiedzy!

Szybkie Quizy CKE

Zweryfikuj to, co właśnie przeczytałeś. Krótkie testy wiedzy (ABCD) z systemów liczbowych, bramek i sieci. Wynik natychmiast.

Praktyka i Arkusze

Zobacz, jak zadania z tego działu wyglądają na prawdziwych arkuszach. Pobierz pliki CKE i rozwiązania ekspertów krok po kroku.

← Wróć do spisu treści teorii