W arkuszu dostajesz kilkanaście linijek pseudokodu i pytanie, co wypisze dla podanego n. Zmienia się treść algorytmu, nie sposób jego rozgryzienia: tabelka śledzenia zmiennych działa tak samo na silni, jak na sortowaniu. Do tego dochodzi drugie stałe pytanie, o złożoność, którą rozpoznasz po liczbie zagnieżdżonych pętli. Na zajęciach widzimy, że gubi się nie sam algorytm, tylko kolejność wykonania — co dzieje się w zagnieżdżonej pętli i które instrukcje zdążyły się wykonać do danego momentu.

Ś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$ ?". Komputer stoi na stanowisku przez cały egzamin, ale przepisywanie pseudokodu do środowiska bywa wolniejsze niż rzetelna tabelka — a przy pytaniu o złożoność i tak nic nie da.

💡 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!$ ).

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"

Przeczytaj też

Najczęstsze błędy na maturze z informatyki

Lista pomyłek, które kosztują punkty mimo poprawnego rozumowania — i sposoby, żeby ich uniknąć.

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

Śledzenie pseudokodu i złożoność obliczeniowa

Ś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ść?

Zdajesz maturę rozszerzoną z informatyki?

Nadal czujesz się niepewnie?

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)