Śledzenie pseudokodu i złożoność obliczeniowa - Pewniak Maturalny 2026

Śledzenie algorytmu (Zostań ludzkim kompilatorem)

Na maturze często spotkasz się z zadaniem, w którym CKE rzuca Ci krótki pseudokod i pyta: "Jaki wynik wypisze ten algorytm dla $n = 5$ ?". Nie masz do dyspozycji komputera, więc musisz polegać na kartce i własnym umyśle.

💡 Twoja tajna broń: Tabelka śledzenia (Dry Run)

Najskuteczniejszą, całkowicie bezbłędną metodą analizy jest tabelka śledzenia zmiennych. Polega ona na wypisaniu wszystkich zmiennych z algorytmu w postaci nagłówków kolumn. Następnie przechodzisz linijka po linijce przez kod i aktualizujesz ich wartości, wykreślając stare.

Jak to wygląda w praktyce?

Najlepiej nauczyć się tego na konkretnym przykładzie z arkusza maturalnego.

Zadanie

Przeanalizuj poniższy pseudokod:

n ← 4
wynik ← 1
DOPÓKI n > 0 WYKONUJ:
  wynik ← wynik * n
  n ← n - 1
WYPISZ wynik

Zbuduj tabelkę śledzenia i podaj ostateczny wynik wypisany przez program.

💡 Pokaż rozwiązanie krok po kroku▼

1
Krok 1: Inicjalizacja (Przed pętlą)
Zapisujemy stan początkowy naszych zmiennych. Mamy $n = 4$ oraz $wynik = 1$ . Sprawdzamy warunek pętli: $4 > 0$ jest prawdą, więc wchodzimy do środka.
2
Krok 2: Pierwszy obrót pętli
Wykonujemy pierwszą instrukcję: wynik ← wynik * n, czyli $1 \cdot 4 = 4$ . Nasza zmienna wynik to teraz 4.
Następnie: n ← n - 1, co daje nam $n = 3$ . Warunek dalej jest spełniony ( $3 > 0$ ).
3
Krok 3: Kompletna tabelka (Aż do fałszu)
Powtarzamy ten proces, aż warunek pętli przestanie być spełniony. Gotowa tabelka na Twojej karcie egzaminacyjnej powinna wyglądać tak:
Krok pętli $n$ wynik Warunek ( $n > 0$ )
Start 4 1 Prawda ( $4 > 0$ )
1 3 4 Prawda
2 2 12 Prawda
3 1 24 Prawda
4 0 24 Fałsz (Koniec)
Odpowiedź: Dzięki tabelce widzimy wyraźnie, że algorytm po zakończeniu wypisze wartość 24 (jest to klasyczny algorytm silni: $4!$ ).

Krok pętli	$n$	wynik	Warunek ( $n > 0$ )
Start	4	1	Prawda ( $4 > 0$ )
1	3	4	Prawda
2	2	12	Prawda
3	1	24	Prawda
4	0	24	Fałsz (Koniec)

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

Złożoność obliczeniowa określa, jak bardzo wydłuża się czas działania algorytmu w zależności od rozmiaru danych wejściowych (oznaczanych w informatyce jako $n$ ).

Na maturze rzadko musisz liczyć każdą matematyczną operację – wystarczy oszacować rząd wielkości. Twoim głównym celem podczas analizy pseudokodu powinno być poszukiwanie pętli.

Jak błyskawicznie rozpoznać złożoność?

🚀 Liniowa: $O(n)$

Najczęstsza na maturze. Pojawia się, gdy mamy tylko jedną pętlę przechodzącą przez elementy. Jeśli ilość danych wzrośnie 10 razy, czas wykonania również wzrośnie 10 razy.

DLA i = 1 DO n WYKONUJ...

🐢 Kwadratowa: $O(n^2)$

Typowa dla np. sortowania bąbelkowego. Rozpoznasz ją po dwóch zagnieżdżonych w sobie pętlach. Jeśli dane wzrosną 10 razy, czas wzrośnie aż 100 razy!

DLA i = 1 DO n: 
  DLA j = 1 DO n...

⚡ Logarytmiczna: $O(\log n)$

Ekstremalnie szybka złożoność! Występuje, gdy z każdym krokiem pętli zbiór danych zmniejsza się o połowę (np. wyszukiwanie binarne).

DOPÓKI lewy < prawy: 
  srodek = (lewy + prawy) / 2

💎 Stała: $O(1)$

Święty Graal programowania. Kod wykonuje się zawsze w tym samym czasie, niezależnie od tego, czy przetwarza 5 elementów, czy 5 miliardów.

if (tablica[0] % 2 == 0): 
  WYPISZ "Parzysta"

Śledzenie algorytmu (Zostań ludzkim kompilatorem)

Jak to wygląda w praktyce?

Zadanie

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

Jak błyskawicznie rozpoznać złożoność?

Nadal czujesz się niepewnie?