Analiza czasu i pamięci algorytmów

1. Wprowadzenie

Analiza algorytmów polega na badaniu dwóch głównych zasobów:

Czas wykonania (Time Complexity) – jak szybko algorytm działa
Pamięć (Space Complexity) – ile pamięci algorytm zużywa

Oba aspekty są równie ważne, choć często większy nacisk kładzie się na czas wykonania.

2. Złożoność czasowa (Time Complexity)

Złożoność czasowa określa, jak liczba operacji rośnie wraz ze wzrostem rozmiaru danych wejściowych.

2.1. Jak mierzyć czas?

Nie mierzymy czasu zegara, ale liczbę podstawowych operacji:

Przypisania
Porównania
Operacje arytmetyczne
Wywołania funkcji

2.2. Przykład analizy

Analiza: - Przypisanie początkowe: 1 - Pętla: n iteracji × 2 operacje = 2n - Return: 1

Łącznie: 1 + 2n + 1 = 2n + 2

Big O: O(n) – ignorujemy stałe i mniejsze składniki.

3. Złożoność pamięciowa (Space Complexity)

Złożoność pamięciowa określa, ile dodatkowej pamięci potrzebuje algorytm (poza danymi wejściowymi).

3.1. Co wlicza się do pamięci?

Zmienne lokalne
Struktury danych pomocnicze (listy, słowniki itp.)
Stos wywołań (dla rekurencji)

Nie wlicza się: * Danych wejściowych (są dane) * Wyników zwracanych (są wymagane)

3.2. Przykład: Suma elementów

Złożoność pamięciowa: O(1) – używamy tylko jednej zmiennej suma.

3.3. Przykład: Kopia listy

Złożoność pamięciowa: O(n) – tworzymy nową listę o rozmiarze n.

4. Analiza iteracyjna vs rekurencyjna

4.1. Wersja iteracyjna

Złożoność czasowa: O(n) Złożoność pamięciowa: O(1) – tylko zmienne suma i i.

4.2. Wersja rekurencyjna

Złożoność czasowa: O(n) Złożoność pamięciowa: O(n) – każde wywołanie rekurencyjne dodaje ramkę na stos.

Wnioski: - Rekurencja jest elegantsza, ale zużywa więcej pamięci. - Dla dużych n może wystąpić stack overflow.

5. Przykład: Fibonacci

5.1. Rekurencja bez optymalizacji

Złożoność czasowa: O(2ⁿ) – drzewo wywołań rośnie wykładniczo. Złożoność pamięciowa: O(n) – głębokość stosu wywołań.

Problem: - fibonacci_rekurencja(40) zajmuje kilka sekund - fibonacci_rekurencja(100) – praktycznie niemożliwe

5.2. Fibonacci z memoizacją

Złożoność czasowa: O(n) – każda wartość obliczana tylko raz. Złożoność pamięciowa: O(n) – słownik memo + stos wywołań.

5.3. Fibonacci iteracyjnie

Złożoność czasowa: O(n) Złożoność pamięciowa: O(1) – tylko dwie zmienne.

Wnioski: - Iteracja jest najlepsza pod względem pamięci. - Memoizacja znacznie przyspiesza rekurencję.

6. Trade-off: Czas vs Pamięć

Często musimy wybierać między szybkością a zużyciem pamięci.

Przykład: Sprawdzanie, czy liczba była już widziana

Wariant 1: Bez dodatkowej pamięci

Czas: O(n) Pamięć: O(1)

Wariant 2: Z użyciem zbioru

Czas: O(n) – sprawdzanie w zbiorze to O(1) Pamięć: O(n) – zbiór widziane

Trade-off: Poświęcamy pamięć, aby przyspieszyć wyszukiwanie.

7. Analiza sortowania

7.1. Sortowanie bąbelkowe

Czas: - Najgorszy przypadek: O(n²) - Najlepszy przypadek (już posortowana): O(n)

Pamięć: O(1) – sortowanie w miejscu

7.2. Merge Sort

Czas: O(n log n) – zawsze, niezależnie od danych Pamięć: O(n) – tworzymy dodatkowe listy

Porównanie:

Algorytm	Czas (najgorszy)	Pamięć	Stabilny?
Sortowanie bąbelkowe	O(n²)	O(1)	Tak
Merge Sort	O(n log n)	O(n)	Tak
Quick Sort	O(n²)	O(log n)	Nie
Heap Sort	O(n log n)	O(1)	Nie

8. Praktyczne mierzenie czasu w Pythonie

8.1. Moduł `time`

8.2. Moduł `timeit`

8.3. Profiler wbudowany

Wynik pokazuje: - Liczbę wywołań funkcji - Całkowity czas - Czas na wywołanie

9. Praktyczne mierzenie pamięci w Pythonie

9.1. Moduł `sys`

9.2. Moduł `tracemalloc`

10. Optymalizacja algorytmów

10.1. Unikanie niepotrzebnych obliczeń

Źle:

Dobrze:

10.2. Używanie wbudowanych funkcji

Źle:

Dobrze:

10.3. List comprehension vs pętla

Wolniejsze:

Szybsze:

10.4. Generator vs lista (oszczędność pamięci)

Więcej pamięci:

Mniej pamięci:

11. Amortyzowana złożoność czasowa

Niektóre operacje są zazwyczaj szybkie, ale czasami wolniejsze.

Przykład: `list.append()` w Pythonie

Analiza: - Większość append() to O(1) - Czasami lista musi być realokowana → O(n)

Amortyzowana złożoność: O(1) – średnio każda operacja jest stała.

12. Porównanie popularnych operacji w Pythonie

Operacja	Lista	Zbiór (set)	Słownik (dict)
Dostęp po indeksie	O(1)	–	O(1) (po kluczu)
Wyszukiwanie elementu	O(n)	O(1)	O(1)
Dodanie elementu	O(1)*	O(1)	O(1)
Usunięcie elementu (wartość)	O(n)	O(1)	O(1)
Sortowanie	O(n log n)	–	–

*amortyzowane

13. Przykład kompleksowej analizy

Problem: Znalezienie duplikatów w liście

Rozwiązanie 1: Dwie pętle (naiwne)

Czas: O(n²) Pamięć: O(k), gdzie k to liczba duplikatów

Rozwiązanie 2: Użycie zbioru

Czas: O(n) Pamięć: O(n)

Rozwiązanie 3: Użycie Counter