Big O Notation: Co faktycznie oczekuje się od nas na A-Level w informatyce

Notacja Big O pojawia się w każdej ważnej specyfikacji A-level z informatyki (AQA, OCR, Edexcel) i myli wielu uczniów nie dlatego, że matematyka jest trudna, ale dlatego, że nigdy nie widzą jej powiązanej z rzeczywistym kodem. To praktyczne omówienie tego, co musisz wiedzieć i jak odpowiedzieć na pytania egzaminacyjne na ten temat bez gadania nie na temat.

Co Big O faktycznie mierzy

Big O opisuje, jak czas działania (lub użycie pamięci) algorytmu rośnie wraz ze wzrostem rozmiaru wejścia, zwykle oznaczanego jako n. To nie jest pomiar stopera w sekundach. To sposób opisania tempa wzrostu, dzięki czemu możesz porównywać algorytmy niezależnie od sprzętu.

Gdy napiszesz O(n), mówisz: jeśli podwoję wejście, praca mniej więcej się podwoi. O(n²) oznacza, że podwojenie wejścia mniej więcej czterokrotnie zwiększa pracę. Ten związek to to, co egzaminatorzy chcą, abyś zidentyfikował, a nie dokładne liczby operacji.

Złożoności, które musisz znać doskonale

Dla A-level to są te, które pojawiają się raz za razem:

• O(1) – czas stały. Dostęp do elementu tablicy po indeksie: arr[5]. Nie ma znaczenia, jak duża jest tablica.
• O(log n) – logarytmiczne. Wyszukiwanie binarne na posortowanej liście. Każdy krok zmniejsza o połowę pozostałą przestrzeń wyszukiwania.
• O(n) – liniowe. Pojedyncza pętla przez listę, jak wyszukiwanie liniowe sprawdzające każdy element raz.
• O(n log n) – linearytmiczne. Merge sort i quicksort (średni przypadek) znajdują się tutaj.
• O(n²) – kwadratowe. Zagnieżdżone pętle na tych samych danych, co dokładnie robią bubble sort, insertion sort i selection sort.
• O(2ⁿ) – wykładnicze. Naiwna rekurencyjna sekwencja Fibonacciego bez memoizacji. Szybko się pogarsza.

Powinieneś umieć spojrzeć na pseudokod i powiedzieć, który z nich to jest od razu, bo to głównie to, co się testuje.

Czytanie kodu pod kątem złożoności

Metoda, która zawsze działa: policz pętle i zobacz, jak się mają do n.

# O(n) - jedna pętla, jeden przebieg
for i in range(n):
    print(i)

# O(n^2) - zagnieżdżona pętla, obie związane z n
for i in range(n):
    for j in range(n):
        print(i, j)

# O(log n) - przestrzeń wyszukiwania zmniejsza się o połowę w każdej iteracji
low, high = 0, n - 1
while low <= high:
    mid = (low + high) // 2
    if target == arr[mid]:
        break
    elif target < arr[mid]:
        high = mid - 1
    else:
        low = mid + 1

Zagnieżdżona pętla, gdzie zakres pętli wewnętrznej zależy od n, to nadal O(n²), nawet jeśli wygląda nieco inaczej (jak for j in range(i) zamiast for j in range(n) — to nadal jest kwadratowe ogółem, tylko z różnicą w czynniku stałym).

Uwaga na pętle, które wcale nie zależą od n. Pętla, która zawsze wykonuje się 10 razy niezależnie od rozmiaru wejścia, to O(1), nawet jeśli pętla jest obecna. Egzaminatorzy lubią to podkradać.

Typowe algorytmy sortowania i ich Big O

To ulubiony temat egzaminacyjny, ponieważ łączy dwie specyfikacje jednocześnie: algorytmy sortowania i złożoność.

Algorytm	Najlepszy przypadek	Najgorszy przypadek
Bubble sort	O(n)	O(n²)
Insertion sort	O(n)	O(n²)
Merge sort	O(n log n)	O(n log n)
Binary search	O(1)	O(log n)
Linear search	O(1)	O(n)

Spójność merge sort (ta sama złożoność w najlepszym i najgorszym przypadku) warta jest wyraźnego wspomnienia, jeśli pytanie pyta, dlaczego wybrałbyś go zamiast bubble sort dla dużych zbiorów danych. Najlepszy przypadek bubble sort O(n) dotyczy tylko z optymalizacją wczesnego wyjścia, gdy w przebiegu nie ma zamiany — wspomnieć ten szczegół, jeśli go poднiesiesz, ponieważ niektóre komisje egzaminacyjne go oczekują.

Gdzie uczniowie tracą punkty

Najważniejszy: pisanie