BLOK 02 · 2 godz. O(n) Efektywność

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

Informatyka Rozszerzona · Klasa 4 · Semestr I · Blok 02/30

1. Po co mierzyć efektywność algorytmu?

Dwa programy mogą dawać ten sam wynik, ale jeden policzy go w milisekundę, a drugi — dla dużych danych — będzie liczył godzinami. Złożoność obliczeniowa to sposób opisania, jak czas (lub pamięć) potrzebny na wykonanie algorytmu rośnie wraz z rozmiarem danych wejściowych n.

Notacja O (duże O)

Opisuje górne ograniczenie tempa wzrostu liczby operacji w najgorszym przypadku, w miarę jak n rośnie do nieskończoności. Nie interesuje nas dokładna liczba kroków — interesuje nas kształt wzrostu.

Najczęstsze klasy złożoności — od najlepszej do najgorszej

Notacja	Nazwa	Przykład	n = 1 000 000 → liczba operacji (orientacyjnie)
O(1)	Stała	Dostęp do elementu tablicy po indeksie	1
O(log n)	Logarytmiczna	Wyszukiwanie binarne	~20
O(n)	Liniowa	Przejście przez wszystkie elementy tablicy	1 000 000
O(n log n)	Liniowo-logarytmiczna	MergeSort, QuickSort (śr.)	~20 000 000
O(n²)	Kwadratowa	Dwie zagnieżdżone pętle po tej samej tablicy	10¹²
O(2ⁿ)	Wykładnicza	Naiwna rekurencja Fibonacciego bez memoizacji	astronomiczna

2. Jak liczyć złożoność — pętle

Pętla pojedyncza → O(n)

for i in range(n):
    print(i) # n razy

Jedna pętla przechodząca przez n elementów wykonuje n operacji — złożoność liniowa.

Pętle zagnieżdżone (niezależne rozmiary) → O(n²)

for i in range(n):
    for j in range(n):
        print(i, j) # n × n razy

Pętla wewnętrzna wykonuje się n razy dla każdego przebiegu pętli zewnętrznej — razem n × n = n² operacji.

Pętla jednolita, ale z podziałem → O(log n)

i = n
while i > 1:
    i = i // 2 # dzielimy przez 2 w każdym kroku

Jeśli w każdym kroku rozmiar problemu zmniejsza się o połowę, liczba kroków potrzebnych do dojścia do 1 wynosi log₂(n) — stąd wyszukiwanie binarne jest tak szybkie.

Najczęstszy błąd uczniów

Dwie pętle jedna po drugiej (nie zagnieżdżone!) to nadal O(n), a nie O(n²) — bo n + n = 2n, a stałe mnożniki pomijamy w notacji O.

3. Ćwiczenia praktyczne

Ćwiczenie 1 — Określ złożoność

Jaka jest złożoność poniższego fragmentu?

for i in range(n):
    for j in range(i, n):
        print(i, j)

O(n²). Mimo że pętla wewnętrzna skraca się z każdym przebiegiem (od i do n), suma liczby kroków to w przybliżeniu n²/2 — a stałe (½) pomijamy w notacji O, więc nadal jest to klasa kwadratowa.

Ćwiczenie 2 — Zaprojektuj eksperyment

Napisz w Pythonie funkcję suma_liniowa(n) sumującą liczby od 1 do n w pętli, oraz porównaj jej czas działania z wbudowanym wzorem n*(n+1)//2 dla n = 10 000 000, korzystając z modułu time. Zanotuj różnicę czasów — to praktyczna ilustracja różnicy między O(n) a O(1).

import time

n = 10_000_000

start = time.perf_counter()
suma = sum(range(1, n+1)) # O(n)
print("Pętla:", time.perf_counter() - start)

start = time.perf_counter()
suma2 = n * (n + 1) // 2 # O(1)
print("Wzór:", time.perf_counter() - start)

4. Sprawdź wiedzę

5. Podsumowanie bloku

Rozumiem, po co stosuje się notację O(n) i co oznacza "najgorszy przypadek".
Potrafię odróżnić złożoność O(n), O(n²) i O(log n) na podstawie struktury pętli w kodzie.
Wiem, że stałe mnożniki i składniki niższego rzędu pomija się w notacji O.
Wykonałem eksperyment porównujący czas działania O(n) i O(1) w Pythonie.

← Blok 01: Organizacja & Diagnoza Blok 03: Rekurencja vs Iteracja →