Algorytmy, w których CKE sprawdza złożoność obliczeniową. Opanuj sortowanie, wyszukiwanie binarne, rekurencję oraz techniki optymalizacji kodu.
Wstęp: Czas to (maturalny) pieniądz
Wchodzimy w świat algorytmów, gdzie nie wystarczy już samo "rozwiązanie problemu". Kod musi wykonać się wystarczająco szybko. CKE celowo dobiera tak duże pliki testowe (np. milion liczb), aby programy napisane w sposób naiwny "zawiesiły się" lub wykonywały przez kilkanaście minut. Ten moduł to zbiór technik, które pozwolą Twoim skryptom działać w ułamku sekundy.
⏱️ Spis treści: Techniki Zaawansowane
1
Sortowanie: Od bąbelków po wbudowane potęgi
Uporządkowanie danych od najmniejszej do największej to najczęstsza operacja na egzaminie. Musisz zrozumieć jak działają klasyczne algorytmy (część teoretyczna) oraz potrafić błyskawicznie używać narzędzi wbudowanych w język Python (część praktyczna).
Klasyk z lekcji informatyki. Polega na wielokrotnym przechodzeniu przez listę i zamianie miejscami par sąsiadujących elementów, jeśli są w złej kolejności. Największe elementy "wypływają" na koniec listy jak bąbelki powietrza. Złożoność wynosi – bardzo wolno!
def sortowanie_babelkowe(T):
n = len(T)
# Pętla wykonuje się n-1 razy
for i in range(n - 1):
# Z każdym krokiem prawa strona jest już posortowana
for j in range(n - 1 - i):
if T[j] > T[j + 1]:
# Zamiana miejscami w Pythonie
T[j], T[j+1] = T[j+1], T[j]
return T
Działa podobnie do układania kart w ręce. Bierzemy kolejny element i "cofamy" się z nim, dopóki nie znajdziemy dla niego właściwego (posortowanego) miejsca. Również ma złożoność , ale dla wstępnie posortowanych danych bywa bardzo szybkie.
def sortowanie_wstawianie(T):
for i in range(1, len(T)):
klucz = T[i]
j = i - 1
# Przesuwamy elementy większe od klucza w prawo
while j >= 0 and klucz < T[j]:
T[j + 1] = T[j]
j -= 1
T[j + 1] = klucz
return T
Na maturze praktycznej nikt nie każe Ci pisać własnego sortowania bąbelkowego. Używamy wbudowanego algorytmu Timsort (złożoność ). Masz do wyboru dwie metody, a rozróżnienie ich to klucz do uniknięcia irytujących błędów w kodzie.
Zmienia oryginalną listę i nic nie zwraca (zwraca None). Nie możesz przypisać jej wyniku do nowej zmiennej!
dane = [5, 2, 8]
dane.sort() # dane to teraz [2, 5, 8]
# dane.sort(reverse=True) - malejąco
Zostawia oryginał w spokoju i zwraca nową, posortowaną listę. Idealna, gdy będziesz jeszcze potrzebować danych w kolejności ich wczytania.
dane = [5, 2, 8]
nowe = sorted(dane)
# nowe to [2, 5, 8]
# dane nadal to [5, 2, 8]!
Zadanie: "Posortuj listę wyrazów, ale nie alfabetycznie, tylko po ich długości." Do obu funkcji (sort i sorted) możemy przekazać specjalny parametr key, podając mu funkcję, według której Python ma oceniać elementy.
slowa = ["Woda", "Sok", "Kawa", "Herbata"]
# Sortowanie po długości (funkcja len)
slowa.sort(key=len)
# Wynik: ['Sok', 'Woda', 'Kawa', 'Herbata']
Użycie wyrażeń Lambda: Często musimy posortować listy 2D po konkretnej kolumnie. Używamy wtedy anonimowych funkcji lambda:
# Lista punktów [x, y]
punkty = [[2, 5], [1, 9], [4, 1]]
# Chcemy posortować po wartości Y (indeks 1)
punkty.sort(key=lambda element: element[1])
# Wynik: [[4, 1], [2, 5], [1, 9]]
2
Wyszukiwanie Binarne (Dychotomia)
Wyobraź sobie szukanie hasła w grubym słowniku. Nie czytasz go słowo po słowie od pierwszej strony. Otwierasz słownik na środku – jeśli szukane słowo jest alfabetycznie "mniejsze" (wcześniej w alfabecie), odrzucasz całą prawą połowę i powtarzasz proces tylko dla lewej. Na tym polega wyszukiwanie binarne.
Warunek absolutny: Aby użyć wyszukiwania binarnego, zbiór danych MUSI BYĆ POSORTOWANY (lub funkcja musi być monotoniczna). Złożoność tego algorytmu to , co oznacza, że w tablicy liczącej milion elementów (gdzie naiwne wyszukiwanie wykona milion kroków), wyszukiwanie binarne znajdzie wynik w maksymalnie 20 krokach!
Używamy dwóch "wskaźników" (zmiennych): lewy i prawy, które wyznaczają początek i koniec przeszukiwanego przedziału. W każdym kroku obliczamy środek i sprawdzamy, w której połówce może kryć się nasza liczba.
def szukaj_binarnie(T, szukana):
lewy = 0
prawy = len(T) - 1
# Dopóki przedział ma jakikolwiek rozmiar
while lewy <= prawy:
# Dzielenie całkowite (//), bo indeks musi być intem
srodek = (lewy + prawy) // 2
if T[srodek] == szukana:
return srodek # Znaleziono! Zwracamy pozycję
elif T[srodek] < szukana:
lewy = srodek + 1 # Szukana jest po prawej
else:
prawy = srodek - 1 # Szukana jest po lewej
return -1 # Jeśli pętla się skończy i nic nie znajdzie
Zadanie: dla jakiego argumentu wartość funkcji ? Wymóg CKE: na krańcach przedziału funkcja musi mieć różne znaki (czyli ), co gwarantuje, że wykres przecina oś X.
Ponieważ pracujemy na liczbach zmiennoprzecinkowych (ułamkach), nie szukamy dokładnego zera, lecz przerywamy pętlę, gdy przedział stanie się mniejszy niż narzucona dokładność (epsilon).
def f(x):
return x**3 - 2*x - 5 # Nasza funkcja
def miejsce_zerowe(a, b, epsilon):
# Sprawdzamy, czy a i b nie są już miejscami zerowymi
if f(a) == 0: return a
if f(b) == 0: return b
# Dopóki szerokość przedziału jest większa niż dokładność
while abs(a - b) > epsilon:
# Zwykłe dzielenie (/), bo szukamy ułamków
srodek = (a + b) / 2
# Trafiliśmy w punkt
if f(srodek) == 0:
return srodek
# Sprawdzamy znaki: czy przecina oś po lewej stronie?
if f(a) * f(srodek) < 0:
b = srodek # Zacieśniamy z prawej
else:
a = srodek # Zacieśniamy z lewej
# Zwracamy przybliżoną wartość
return (a + b) / 2
3
Rekurencja: Magia wywoływania samej siebie
Rekurencja to technika programistyczna, w której funkcja w trakcie działania wywołuje samą siebie, aby rozwiązać mniejszy fragment tego samego problemu. Aby komputer nie zapętlił się w nieskończoność (błąd RecursionError), każda funkcja rekurencyjna musi posiadać żelazny warunek stopu – moment, w którym przestaje wywoływać samą siebie i zaczyna zwracać wyniki.
Silnia z liczby (zapisywana jako ) to iloczyn wszystkich liczb od do . Matematycznie możemy to zapisać jako . To idealny wzór dla algorytmu rekurencyjnego.
def silnia(n):
# 1. Warunek stopu (baza)
if n == 0:
return 1
# 2. Wywołanie rekurencyjne (krok)
return n * silnia(n - 1)
Wyobraź to sobie jak stos: funkcja "czeka" z mnożeniem, aż silnia z mniejszej liczby zwróci jej gotowy wynik.
Kolejny wyraz ciągu to suma dwóch poprzednich. Zapis naiwny wygląda pięknie, ale wykonuje te same obliczenia setki razy! Złożoność tego kodu to – policzenie 40. wyrazu "zawiesi" komputer na kilka sekund, a 100. wyrazu... obliczałoby się latami.
def fib(n):
# Warunek stopu (dla fib(0) = 0 i fib(1) = 1)
if n <= 1:
return n
# Podwójne wywołanie! (Drzewo eksploduje)
return fib(n - 1) + fib(n - 2)
Zadanie polega na przeniesieniu stosu krążków z jednego palika na inny, posiłkując się trzecim palikiem. Zasada główna: nie można położyć większego krążka na mniejszym. CKE uwielbia pytać o to, ile kroków zajmie przeniesienie krążków (odpowiedź to zawsze ), lub prosi o prześledzenie pierwszych wywołań funkcji.
def hanoi(n, skad, dokad, pomocniczy):
# Wykonuj dopóki są jakieś krążki (n > 0)
if n > 0:
# 1. Przenieś wieżę n-1 na palik pomocniczy
hanoi(n - 1, skad, pomocniczy, dokad)
# 2. Przenieś największy krążek na miejsce docelowe
print(f"Przenieś krążek z {skad} na {dokad}")
# 3. Przenieś wieżę n-1 z pomocniczego na docelowy
hanoi(n - 1, pomocniczy, dokad, skad)
Magia kodu polega na zamianie argumentów (palików) miejscami w każdym wywołaniu rekurencyjnym. Aby przenieść wieżę z A na C:
Domyślnie Python pozwala na maksymalnie 1000 głębokości rekurencji (aby uniknąć zablokowania pamięci RAM - tzw. Stack Overflow). Jeśli w zadaniu maturalnym musisz przejść rekurencyjnie przez listę dłuższą niż tysiąc elementów, Twój program rzuci błąd.
import sys
sys.setrecursionlimit(5000) # Ratunek w sytuacjach krytycznych!
4
Techniki Optymalizacji: Wyższy Poziom Kodu
Kiedy naiwne pętle for wewnątrz innych pętli for (czyli złożoność ) sprawiają, że Twój program działa za wolno, musisz sięgnąć po techniki optymalizacyjne. Są to maturalne "wytrychy", które pozwalają skrócić czas wykonywania operacji na wielkich zbiorach danych do absolutnego minimum.
Problem: Masz tablicę miliona liczb i musisz 100 000 razy podać sumę elementów na przedziale od indeksu do . Zwykła pętla "zawiezie" program.
Rozwiązanie: Tworzymy dodatkową tablicę, w której zapisujemy narastającą sumę elementów od początku (tzw. prefiks). Dzięki temu sumę dowolnego przedziału możemy obliczyć wykonując tylko jedno odejmowanie: . Czas działania to !
T = [2, 4, 1, 5, 3]
# Budowanie tablicy sum prefiksowych
pref = [0] * len(T)
pref[0] = T[0]
for i in range(1, len(T)):
pref[i] = pref[i-1] + T[i]
# Szybkie pytanie o sumę T[1] do T[3]
suma_1_do_3 = pref[3] - pref[0] # (12 - 2 = 10)
Polegają na podejmowaniu decyzji, która w danym momencie wydaje się najlepsza, nie martwiąc się o przyszłość. Najczęstszy przypadek to problem wydawania reszty z użyciem jak najmniejszej liczby monet. Zawsze bierzemy największy nominał, jaki się jeszcze mieści.
def wydaj_reszte(kwota):
nominaly = [500, 200, 100, 50, 20, 10, 5, 2, 1]
wynik = {}
for n in nominaly:
if kwota >= n:
# Ile sztuk danego nominału mieści się w kwocie?
ilosc = kwota // n
wynik[n] = ilosc
# Obliczamy pozostałą resztę do wydania
kwota = kwota % n
return wynik
Wyobraź sobie zadanie: "Znajdź w tablicy (zawierającej tylko liczby dodatnie) spójny podciąg, którego suma wynosi dokładnie S". Naiwne podejście wymagałoby podwójnej pętli for. Metoda gąsienicy pozwala to zrobić w jednym przejściu (złożoność ).
Używamy dwóch "wskaźników" (zmiennych): Głowy i Ogona. Gąsienica "zjada" liczby, rozciągając Głowę do przodu. Gdy zje za dużo (suma jest większa niż ), podciąga Ogon z tyłu, "wypluwając" liczby, aż suma znowu będzie odpowiednia.
def gasienica(T, cel):
ogon = 0
suma_obecna = 0
# Glowa idzie do przodu w petli for
for glowa in range(len(T)):
suma_obecna += T[glowa] # Zjadamy nową liczbę
# Jeśli zjedliśmy za dużo, podciągamy ogon
while suma_obecna > cel and ogon <= glowa:
suma_obecna -= T[ogon] # Wypluwamy liczbę z tyłu
ogon += 1 # Przesuwamy ogon
# Trafiliśmy w punkt!
if suma_obecna == cel:
return True, ogon, glowa # Zwracamy indeksy przedziału
return False # Nie znaleziono takiego podciągu
Właśnie domknęliśmy najtrudniejszy, szósty dział naszego kursu. Od wczytywania plików po zaawansowane wyszukiwanie binarne i metody optymalizacji – masz teraz w swoim koderskim arsenale wszystko, czego CKE może od Ciebie wymagać na maturze z informatyki. Pora wykorzystać to w praktyce!
Przejdź do: Baza Zadań Maturalnych ➡️