Złożoność obliczeniowa i notacja O

Ocena efektywności algorytmu przewija się przez całą maturę z informatyki na poziomie rozszerzonym: podstawa programowa wymaga, by uczeń porównywał działanie różnych algorytmów, analizował je na podstawie gotowych implementacji, oceniał ich efektywność i posługiwał się pojęciem logarytmu. Ten materiał zbiera te umiejętności w jednym miejscu — nie przy konkretnym algorytmie, lecz jako narzędzie, którego używasz przy każdym zadaniu.

Zaczynasz od klas złożoności i ich kolejności: stała, logarytmiczna, liniowa, liniowo-logarytmiczna, kwadratowa i wykładnicza. Uczysz się upraszczać wyrażenia: w notacji O pomija się stałe mnożniki i składniki niższego rzędu, więc $3n^2 + 100n + 7$ to $O(n^2)$, a $\frac{n(n-1)}{2}$ — również $O(n^2)$.

Najważniejsza część to liczenie operacji w kodzie. Śledzisz krótkie programy w Pythonie i C++: zagnieżdżone pętle, w których wewnętrzna zależy od zewnętrznej, pętlę z podwajaną zmienną sterującą (logarytmiczna liczba obrotów) i połączenie obu, które daje $O(n\log n)$. Rozróżniasz pętle wykonywane jedna po drugiej, których koszty się dodaje, od zagnieżdżonych, których koszty się mnoży.

Następnie przekładasz złożoność na praktykę: o ile wydłuży się działanie programu kwadratowego po podwojeniu danych, od jakiego rozmiaru danych algorytm liniowy z dużą stałą wygrywa z kwadratowym i czy program o danej złożoności zmieści się w czasie, jeśli komputer wykonuje około $10^8$ prostych operacji na sekundę. Porównujesz też naiwną rekurencję dla ciągu Fibonacciego, która rośnie wykładniczo, z wersją iteracyjną, oraz złożoność pamięciową działań w miejscu i z kopią danych.

Materiał oferuje cztery formy pracy. Quiz zawiera zadania z analizy kodu i porównywania algorytmów z wyjaśnieniem liczenia operacji. Fiszki utrwalają klasy złożoności z przykładami i reguły upraszczania. Egzamin ustny w formie rozmowy z egzaminatorem sprawdza, czy umiesz ocenić złożoność fragmentu kodu i uzasadnić wybór algorytmu. Praca pisemna do wydruku zawiera zadania otwarte: liczenie operacji, szacowanie czasu działania i porównanie dwóch rozwiązań tego samego problemu.

Wszystkie zadania są oryginalnymi ćwiczeniami do samodzielnej nauki, a liczby obrotów pętli zostały sprawdzone przez uruchomienie programów.

• Porządkujesz klasy złożoności od najwolniej do najszybciej rosnącej.
• Upraszczasz wyrażenia, pomijając stałe i składniki niższego rzędu.
• Liczysz obroty pętli zagnieżdżonych i pętli z podwajaniem zmiennej.
• Szacujesz czas działania programu dla danego rozmiaru danych.
• Porównujesz złożoność czasową i pamięciową różnych rozwiązań tego samego problemu.

Materiał ćwiczeniowy przygotowany przez Zestly.