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

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.

Zapis CKE — co znaczy każdy symbol

Pseudokod w arkuszach ma swoją stałą konwencję i warto ją znać na pamięć, bo połowa błędów w tym zadaniu bierze się nie z algorytmu, tylko z przeczytania zapisu po swojemu.

x ← 5              podstawienie: "wstaw 5 do x"
x = 5              porownanie: "czy x rowna sie 5"
x ≠ 5              roznica; czasem zapisywane jako x <> 5

dla i = 1 do n wykonuj:        petla przechodzi TAKZE przez n
dla i = n do 1 krok -1:        petla malejaca
dopoki warunek wykonuj:        warunek sprawdzany PRZED wejsciem
powtarzaj ... az warunek:      cialo wykona sie co najmniej raz

jezeli warunek to:
  ...
w przeciwnym razie:
  ...

n div 2            dzielenie calkowite: 7 div 2 = 3
n mod 2            reszta z dzielenia:  7 mod 2 = 1
T[i]               i-ty element tablicy
|T|  albo  dlugosc(T)   liczba elementow tablicy
zwroc x            zakonczenie funkcji z wynikiem

Indeksowanie. CKE numeruje elementy tablicy zwykle od 1, a Python i większość języków od zera. Przepisując algorytm z arkusza do środowiska, to jest pierwsze miejsce, w którym wynik się rozjeżdża o jeden element.

Wcięcia. W pseudokodzie CKE nie ma nawiasów klamrowych — o tym, co należy do pętli, decyduje wyłącznie wcięcie. Zanim zaczniesz liczyć, zaznacz sobie ołówkiem, gdzie kończy się ciało pętli.

Strzałka a równość. W treściach zadań = prawie zawsze oznacza porównanie. Jeśli pomylisz je z podstawieniem, cała tabelka śledzenia wyjdzie błędna.

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"

🔀 Liniowo-logarytmiczna: $O(n \log n)$

Rząd dobrych algorytmów sortowania — przez scalanie i szybkiego. Rozpoznasz po tym, że dane są dzielone na pół, a na każdym poziomie podziału przechodzi się przez wszystkie elementy.

sortuj(lewa polowa) 
sortuj(prawa polowa) 
scal wyniki

💣 Wykładnicza: $O(2^n)$

Rekurencja z dwoma wywołaniami w jednym kroku, jak naiwny Fibonacci, albo sprawdzanie wszystkich podzbiorów. Przy $n = 50$ program nie skończy pracy za twojego życia.

zwroc f(n-1) + f(n-2)

Z pseudokodu do działającego kodu

W części praktycznej masz komputer, więc najpewniejszą metodą sprawdzenia własnej tabelki jest przepisanie algorytmu i uruchomienie go. Poniżej ten sam pseudokod obok gotowego kodu — zwróć uwagę na trzy miejsca, w których zapis się zmienia.

PSEUDOKOD CKE                      PYTHON

s ← 0                              s = 0
dla i = 1 do n wykonuj:            for i in range(1, n + 1):
  s ← s + T[i]                       s = s + T[i - 1]
WYPISZ s                           print(s)

range(1, n + 1), a nie range(1, n) — pseudokod CKE obejmuje wartość końcową.
T[i - 1], bo tablica w arkuszu jest numerowana od 1, a w Pythonie od 0.
// zamiast div, % zamiast mod, == zamiast pojedynczego = w warunku.

Przy pytaniu o złożoność komputer nic nie da — tam liczy się umiejętność policzenia pętli. Ale przy pytaniu „co wypisze algorytm” uruchomienie kodu zamienia zadanie za kilka punktów w formalność, o ile pamiętasz o tych trzech różnicach.

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 →