Złożoność algorytmów - Tempo ekspedycji

Witaj z powrotem, @name! Darwin tutaj z nową umiejętnością przetrwania w programowaniu.

Wyobraź sobie, że planujesz ekspedycję przez dżunglę. Możesz wybrać różne trasy:

• Trasa A: Zawsze zajmuje 2 godziny, niezależnie od wielkości zespołu
• Trasa B: 1 godzina na osobę (zespół 10 osób = 10 godzin)
• Trasa C: Każdy musi sprawdzić z każdym ekwipunek (10 osób = 45 par = 45 godzin!)

To analogia do złożoności algorytmów - mierzenia jak szybko rośnie czas wykonania w zależności od wielkości danych. To kluczowa umiejętność dla każdego programisty!

Czym jest złożoność algorytmu?

Złożoność obliczeniowa (computational complexity) to miara opisująca jak szybko rośnie czas wykonania lub zużycie pamięci algorytmu wraz ze wzrostem rozmiaru danych wejściowych.

Używamy notacji Big O (czyt. "Big Oh") do opisania "najgorszego scenariusza" dla algorytmu.

1# Przykład: Szukanie gatunku w dzienniku
2
3# Wersja 1: Prosty dziennik (lista)
4species_list = ["Python", "Leo", "Elephas", "Gorilla", ...]  # n elementów
5
6def find_species_v1(name):
7    """Musimy sprawdzić każdy element - O(n)"""
8    for species in species_list:  # Potencjalnie n iteracji
9        if species == name:
10            return True
11    return False
12
13# Wersja 2: Słownik
14species_dict = {"Python": {...}, "Leo": {...}, ...}
15
16def find_species_v2(name):
17    """Sprawdzamy tylko hash - O(1)"""
18    return name in species_dict  # Stały czas!

Pytanie: Który algorytm jest szybszy dla 1,000,000 gatunków?

• Lista: Potencjalnie sprawdzi 1,000,000 elementów
• Słownik: Sprawdzi 1 element (dzięki hashowaniu)

Notacja Big O - podstawy

Big O opisuje jak algorytm skaluje się wraz ze wzrostem danych.

Składnia: O(wyrażenie), gdzie

n

= rozmiar danych wejściowych

Najczęstsze złożoności (od najszybszych):

| Notacja | Nazwa | Przykład | Opis | |---------|-------|----------|------| | O(1) | Stała | Dostęp dict[key] | Zawsze ten sam czas | | O(log n) | Logarytmiczna | Binary search | Dzieli problem na pół | | O(n) | Liniowa | Pętla przez listę | Raz każdy element | | O(n log n) | Liniowo-log | Sortowanie merge/quick | Dziel i zwyciężaj | | O(n²) | Kwadratowa | Zagnieżdżone pętle | Każdy z każdym | | O(2ⁿ) | Wykładnicza | Wszystkie podzbiory | BARDZO wolne! | | O(n!) | Silnia | Wszystkie permutacje | EKSTREMALNIE wolne! |

Safari analogia

1# O(1) - Stała
2# Jak sprawdzenie mapy - zawsze ta sama ilość czasu
3def get_camp_location(camp_id):
4    """Dostęp do słownika = O(1)"""
5    camps = {1: "Północ", 2: "Południe", 3: "Wschód"}
6    return camps[camp_id]
7
8# O(n) - Liniowa
9# Jak przejście szlakiem - im dłuższy, tym więcej czasu
10def count_species(discovered):
11    """Pętla przez n elementów = O(n)"""
12    count = 0
13    for species in discovered:  # n iteracji
14        count += 1
15    return count
16
17# O(n²) - Kwadratowa
18# Jak porównanie każdego z każdym w zespole
19def find_duplicates(team_members):
20    """Zagnieżdżone pętle = O(n²)"""
21    duplicates = []
22    for i, member1 in enumerate(team_members):  # n iteracji
23        for j, member2 in enumerate(team_members):  # n iteracji każda!
24            if i != j and member1 == member2:
25                duplicates.append(member1)
26    return duplicates

O(1) - Stała złożoność

Definicja: Czas wykonania nie zależy od rozmiaru danych.

1# Operacje O(1):
2
3# 1. Dostęp do elementu listy przez indeks
4animals = ["Tygrys", "Słoń", "Papuga", "Lew"]
5first = animals[0]  # O(1) - bezpośredni dostęp
6
7# 2. Dostęp do słownika przez klucz
8catalog = {"Python": "Pyton", "Leo": "Lew"}
9value = catalog["Python"]  # O(1) - hashing
10
11# 3. Dodawanie na koniec listy (amortized)
12animals.append("Goryl")  # O(1)
13
14# 4. Sprawdzanie długości
15length = len(animals)  # O(1) - Python przechowuje długość
16
17# 5. Operacje matematyczne
18result = 5 + 3  # O(1)
19result = 100 ** 2  # O(1)
20
21# 6. Sprawdzanie czy element w zbiorze
22species_set = {"Python", "Leo", "Elephas"}
23exists = "Python" in species_set  # O(1) - hashing!

Safari przykład:

1class ExpeditionCamp:
2    """Obóz ekspedycji z O(1) operacjami"""
3
4    def __init__(self):
5        self.supplies = {}  # Słownik dla O(1)
6        self.team_size = 0
7
8    def add_supply(self, item, quantity):
9        """O(1) - dostęp do słownika"""
10        self.supplies[item] = quantity
11
12    def get_supply(self, item):
13        """O(1) - dostęp do słownika"""
14        return self.supplies.get(item, 0)
15
16    def get_team_size(self):
17        """O(1) - zwrócenie wartości"""
18        return self.team_size
19
20# Użycie
21camp = ExpeditionCamp()
22camp.add_supply("Woda", 100)  # O(1)
23water = camp.get_supply("Woda")  # O(1)
24size = camp.get_team_size()  # O(1)

O(n) - Liniowa złożoność

Definicja: Czas wykonania rośnie proporcjonalnie do rozmiaru danych.

1# Operacje O(n):
2
3# 1. Pętla przez wszystkie elementy
4def print_all_species(species):
5    """O(n) - n iteracji"""
6    for s in species:  # n razy
7        print(s)
8
9# 2. Szukanie elementu w liście
10def find_in_list(animals, target):
11    """O(n) - potencjalnie sprawdzi wszystkie"""
12    for animal in animals:  # Maksymalnie n sprawdzeń
13        if animal == target:
14            return True
15    return False
16
17# 3. Sumowanie listy
18def total_distance(distances):
19    """O(n) - przejście przez całą listę"""
20    total = 0
21    for d in distances:  # n iteracji
22        total += d
23    return total
24
25# 4. List comprehension
26squares = [x ** 2 for x in range(n)]  # O(n)
27
28# 5. Kopiowanie listy
29original = [1, 2, 3, 4, 5]
30copy = original[:]  # O(n) - kopiuje n elementów
31
32# 6. Sprawdzanie czy element w liście
33"Python" in animals_list  # O(n) - musi sprawdzić każdy element

Safari przykład:

1def analyze_expedition_log(log):
2    """
3    Analiza dziennika ekspedycji - O(n)
4
5    log: lista wpisów, każdy wpis = {"day": int, "species": int, "distance": float}
6    """
7    total_species = 0
8    total_distance = 0
9
10    # Jedna pętla przez n wpisów = O(n)
11    for entry in log:
12        total_species += entry["species"]
13        total_distance += entry["distance"]
14
15    return {
16        "total_species": total_species,
17        "total_distance": total_distance,
18        "avg_species": total_species / len(log),
19        "avg_distance": total_distance / len(log)
20    }
21
22# Przykład użycia
23log = [
24    {"day": 1, "species": 5, "distance": 12.5},
25    {"day": 2, "species": 3, "distance": 8.0},
26    {"day": 3, "species": 7, "distance": 15.2}
27]
28
29stats = analyze_expedition_log(log)  # O(n) gdzie n = 3
30print(stats)

O(n²) - Kwadratowa złożoność

Definicja: Czas wykonania rośnie proporcjonalnie do kwadratu rozmiaru danych.

Zazwyczaj: Zagnieżdżone pętle!

1# Operacje O(n²):
2
3# 1. Zagnieżdżone pętle - klasyczny przykład
4def print_all_pairs(animals):
5    """O(n²) - każdy z każdym"""
6    for animal1 in animals:  # n iteracji
7        for animal2 in animals:  # n iteracji dla każdej z n
8            print(f"{animal1} i {animal2}")
9    # Łącznie: n * n = n² par
10
11# 2. Bubble sort - proste sortowanie
12def bubble_sort(arr):
13    """O(n²) - w najgorszym przypadku"""
14    n = len(arr)
15    for i in range(n):  # n iteracji
16        for j in range(n - 1):  # ~n iteracji
17            if arr[j] > arr[j + 1]:
18                arr[j], arr[j + 1] = arr[j + 1], arr[j]
19    return arr
20
21# 3. Znajdowanie duplikatów (naiwne)
22def find_duplicates(items):
23    """O(n²) - porównuje każdy z każdym"""
24    duplicates = []
25    for i in range(len(items)):  # n razy
26        for j in range(i + 1, len(items)):  # ~n/2 razy
27            if items[i] == items[j]:
28                duplicates.append(items[i])
29    return duplicates

Dlaczego O(n²) jest problemem?

1import time
2
3def slow_comparison(n):
4    """O(n²) - porównania"""
5    count = 0
6    for i in range(n):
7        for j in range(n):
8            count += 1
9    return count
10
11# Test
12for size in [10, 100, 1000]:
13    start = time.time()
14    result = slow_comparison(size)
15    elapsed = time.time() - start
16    print(f"n={size:4d}: {result:7d} operacji, {elapsed:.6f}s")
17
18# Wyniki:
19# n=  10:     100 operacji, 0.000010s
20# n= 100:   10000 operacji, 0.000850s  (100x więcej danych = 100x dłużej)
21# n=1000: 1000000 operacji, 0.085000s  (1000x więcej = 1,000,000x dłużej!)

Safari przykład - porównywanie wszystkich par lokacji:

1def calculate_all_distances(locations):
2    """
3    O(n²) - oblicza dystans między każdą parą lokacji
4
5    locations: lista krotek (x, y) współrzędnych
6    """
7    import math
8
9    distances = {}
10    n = len(locations)
11
12    # Zagnieżdżone pętle = O(n²)
13    for i in range(n):  # n iteracji
14        for j in range(i + 1, n):  # ~n/2 iteracji każda
15            loc1 = locations[i]
16            loc2 = locations[j]
17
18            # Oblicz dystans euklidesowy
19            dist = math.sqrt((loc1[0] - loc2[0])**2 + (loc1[1] - loc2[1])**2)
20
21            distances[f"{i}-{j}"] = dist
22
23    return distances
24
25# Przykład
26locations = [(0, 0), (3, 4), (6, 8), (1, 1)]
27distances = calculate_all_distances(locations)  # O(4²) = O(16) operacji
28print(distances)
29# {'0-1': 5.0, '0-2': 10.0, '0-3': 1.41..., '1-2': 5.0, '1-3': 3.16..., '2-3': 7.28...}

O(log n) - Logarytmiczna złożoność

Definicja: Czas rośnie logarytmicznie - przy każdym kroku dzielimy problem na pół.

Klasyczny przykład: Binary search (wyszukiwanie binarne)

1def binary_search(sorted_list, target):
2    """
3    O(log n) - dzielimy zakres na pół w każdym kroku
4
5    sorted_list: posortowana lista
6    target: szukana wartość
7    """
8    left = 0
9    right = len(sorted_list) - 1
10
11    while left <= right:
12        mid = (left + right) // 2  # Środek zakresu
13
14        if sorted_list[mid] == target:
15            return mid  # Znaleziono!
16        elif sorted_list[mid] < target:
17            left = mid + 1  # Szukaj w prawej połowie
18        else:
19            right = mid - 1  # Szukaj w lewej połowie
20
21    return -1  # Nie znaleziono
22
23# Przykład
24species = ["Elephas", "Gorilla", "Leo", "Loxodonta", "Panthera", "Python"]
25index = binary_search(species, "Leo")  # O(log 6) = ~2.5 porównań
26print(f"Znaleziono na pozycji: {index}")  # 2
27
28# Porównanie:
29# Linear search (O(n)): Maksymalnie 6 porównań
30# Binary search (O(log n)): Maksymalnie 3 porównania (log₂ 6 ≈ 2.58)

Dlaczego O(log n) jest szybkie?

1# Dla n = 1,000,000 elementów:
2# - O(n): 1,000,000 operacji
3# - O(log n): ~20 operacji (log₂ 1,000,000 ≈ 19.93)
4
5# To 50,000x szybsze!
6
7import math
8
9for n in [10, 100, 1000, 10000, 1000000]:
10    log_n = math.log2(n)
11    print(f"n={n:>7d}: O(n)={n:>7d}, O(log n)={log_n:>5.2f}, ratio={n/log_n:>8.0f}x")
12
13# Wyniki:
14# n=     10: O(n)=     10, O(log n)= 3.32, ratio=       3x
15# n=    100: O(n)=    100, O(log n)= 6.64, ratio=      15x
16# n=   1000: O(n)=   1000, O(log n)= 9.97, ratio=     100x
17# n=  10000: O(n)=  10000, O(log n)=13.29, ratio=     752x
18# n=1000000: O(n)=1000000, O(log n)=19.93, ratio=   50169x

O(n log n) - Liniowo-logarytmiczna

Definicja: Czas rośnie jako n pomnożone przez log n.

Klasyczny przykład: Efektywne algorytmy sortowania (merge sort, quick sort, heap sort)

1def merge_sort(arr):
2    """
3    O(n log n) - dziel i zwyciężaj
4
5    Jak to działa:
6    1. Dziel tablicę na pół (log n poziomów)
7    2. Scal posortowane połówki (n operacji na każdym poziomie)
8    Razem: O(n log n)
9    """
10    if len(arr) <= 1:
11        return arr
12
13    # Podziel na pół
14    mid = len(arr) // 2
15    left = merge_sort(arr[:mid])  # Rekurencja - log n poziomów
16    right = merge_sort(arr[mid:])
17
18    # Scal posortowane połówki - O(n)
19    return merge(left, right)
20
21def merge(left, right):
22    """Scal dwie posortowane listy - O(n)"""
23    result = []
24    i = j = 0
25
26    while i < len(left) and j < len(right):
27        if left[i] < right[j]:
28            result.append(left[i])
29            i += 1
30        else:
31            result.append(right[j])
32            j += 1
33
34    result.extend(left[i:])
35    result.extend(right[j:])
36    return result
37
38# Python's built-in sort() używa Timsort - również O(n log n)
39animals = ["Tygrys", "Słoń", "Papuga", "Lew", "Goryl"]
40sorted_animals = sorted(animals)  # O(n log n)

Porównanie złożoności - praktyczne liczby

| n | O(1) | O(log n) | O(n) | O(n log n) | O(n²) | O(2ⁿ) | |---|------|----------|------|------------|-------|-------| | 10 | 1 | 3 | 10 | 30 | 100 | 1,024 | | 100 | 1 | 7 | 100 | 700 | 10,000 | 1.27×10³⁰ | | 1,000 | 1 | 10 | 1,000 | 10,000 | 1,000,000 | ∞ | | 10,000 | 1 | 13 | 10,000 | 130,000 | 100,000,000 | ∞ |

Wnioski:

• O(1), O(log n), O(n), O(n log n) - dobre dla dużych danych
• O(n²) - ok dla małych danych (<1000 elementów)
• O(2ⁿ), O(n!) - unikaj - tylko dla bardzo małych danych!

Złożoność operacji w Pythonie

Listy

| Operacja | Złożoność | Przykład | |----------|-----------|----------| | Dostęp | O(1) |

arr[5]

| | Append | O(1) |

arr.append(x)

| | Insert | O(n) |

arr.insert(0, x)

| | Delete | O(n) |

arr.remove(x)

| | Search | O(n) |

x in arr

| | Slicing | O(k) |

arr[1:5]

(k=długość slice) | | Copy | O(n) |

arr[:]

| | Sort | O(n log n) |

arr.sort()

|

Słowniki

| Operacja | Złożoność | Przykład | |----------|-----------|----------| | Dostęp | O(1) |

dict[key]

| | Insert | O(1) |

dict[key] = val

| | Delete | O(1) |

del dict[key]

| | Search (key) | O(1) |

key in dict

| | Search (value) | O(n) |

val in dict.values()

|

Zbiory (sets)

| Operacja | Złożoność | Przykład | |----------|-----------|----------| | Add | O(1) |

s.add(x)

| | Remove | O(1) |

s.remove(x)

| | Search | O(1) |

x in s

| | Union | O(n+m) |

s1 \| s2

| | Intersection | O(min(n,m)) |

s1 & s2

|

Praktyczny przykład - optymalizacja

1# PROBLEM: Znajdź duplikaty w liście odkryć
2
3discoveries = ["Python", "Leo", "Elephas", "Python", "Gorilla", "Leo", "Python"]
4
5# ❌ Źle - O(n²)
6def find_duplicates_slow(items):
7    """O(n²) - zagnieżdżone pętle"""
8    duplicates = []
9    for i in range(len(items)):
10        for j in range(i + 1, len(items)):
11            if items[i] == items[j] and items[i] not in duplicates:
12                duplicates.append(items[i])
13    return duplicates
14
15# ✅ Dobrze - O(n)
16def find_duplicates_fast(items):
17    """O(n) - jeden przebieg z set"""
18    seen = set()  # O(1) operacje
19    duplicates = set()
20
21    for item in items:  # O(n)
22        if item in seen:  # O(1) sprawdzenie w set!
23            duplicates.add(item)
24        else:
25            seen.add(item)  # O(1)
26
27    return list(duplicates)
28
29# Porównanie wydajności
30import time
31
32# Dla 1000 elementów:
33large_list = ["Item_" + str(i % 100) for i in range(1000)]
34
35start = time.time()
36result1 = find_duplicates_slow(large_list)  # O(n²) = O(1,000,000)
37time_slow = time.time() - start
38
39start = time.time()
40result2 = find_duplicates_fast(large_list)  # O(n) = O(1,000)
41time_fast = time.time() - start
42
43print(f"Wolna: {time_slow:.4f}s")  # ~0.5s
44print(f"Szybka: {time_fast:.4f}s")  # ~0.0005s
45print(f"Przyspieszenie: {time_slow/time_fast:.0f}x")  # ~1000x szybsze!

Space Complexity - złożoność pamięciowa

Oprócz czasu ważna jest też pamięć!

1# O(1) space - stała pamięć
2def sum_list(arr):
3    """O(1) space - tylko jedna zmienna"""
4    total = 0  # Jedna zmienna niezależnie od n
5    for num in arr:
6        total += num
7    return total
8
9# O(n) space - liniowa pamięć
10def copy_list(arr):
11    """O(n) space - kopiuje całą listę"""
12    return arr[:]  # Nowa lista rozmiaru n
13
14# O(n) space - lista w pamięci
15def squares_list(n):
16    """O(n) space - tworzy listę"""
17    return [x ** 2 for x in range(n)]  # Lista n elementów
18
19# O(1) space - generator!
20def squares_gen(n):
21    """O(1) space - generuje po kolei"""
22    return (x ** 2 for x in range(n))  # Nie tworzy listy!

Zadanie praktyczne

Napisz 3 wersje funkcji sprawdzającej czy lista zawiera duplikaty:

1. Wersja O(n²): Zagnieżdżone pętle
2. Wersja O(n log n): Sortowanie + sprawdzenie sąsiadów
3. Wersja O(n): Używając set

Zmierz czas dla różnych rozmiarów danych (10, 100, 1000, 10000).

Podsumowanie

W tej lekcji nauczyłeś/aś się:

• ✅ Czym jest złożoność obliczeniowa
• ✅ Notacji Big O i jej znaczenia
• ✅ Najczęstszych złożoności: O(1), O(log n), O(n), O(n log n), O(n²)
• ✅ Jak analizować kod pod kątem wydajności
• ✅ Złożoności operacji w Pythonie (lista, dict, set)
• ✅ Jak optymalizować algorytmy
• ✅ Różnicy między time i space complexity

Checkpoint

Przed przejściem dalej:

• [ ] Rozumiesz notację Big O
• [ ] Potrafisz określić złożoność prostych pętli
• [ ] Wiesz dlaczego dict jest szybszy niż list do wyszukiwania
• [ ] Rozumiesz dlaczego zagnieżdżone pętle to O(n²)
• [ ] Znasz różnicę między O(n) a O(log n)
• [ ] Potrafisz optymalizować kod wybierając lepsze struktury danych

Złota zasada: "Przedwczesna optymalizacja to źródło wszelkiego zła" - najpierw napisz działający kod, potem optymalizuj jeśli trzeba!

W następnej lekcji Darwin pokaże Ci algorytmy sortowania - jak klasyfikować odkrycia! 🔢📊