Przypadek Najlepszy, Najgorszy i Średni
Trzy Sposoby Pomiaru Algorytmu
Koszt każdego algorytmu zależy od jego wejścia. Dwa wejścia tego samego rozmiaru mogą powodować zupełnie inne czasy wykonania. Analiza złożoności formalizuje trzy perspektywy na tę zmienność.
Przypadek najlepszy — Ω (Omega): wejście, które sprawia, że algorytm kończy się najszybciej. Dla wyszukiwania liniowego na liście N elementów: Ω(1) — cel znajduje się na pierwszej pozycji. Jedno porównanie, koniec.
Przypadek najgorszy — O (Big O): wejście, które sprawia, że algorytm kończy się najwolniej. Dla wyszukiwania liniowego: O(N) — cel znajduje się na końcu listy lub wcale się nie pojawia. Każdy element wymaga sprawdzenia.
Przypadek średni — Θ (Theta): oczekiwany koszt dla wszystkich możliwych wejść, przy założeniu jednostajnego rozkładu. Dla wyszukiwania liniowego, gdzie cel z równym prawdopodobieństwem może zajmować każdą z N pozycji: Θ(N/2) = Θ(N). Stała 1/2 spada, ponieważ Theta wyraża ścisły wzrost asymptotyczny, a nie dokładne współczynniki.
Dlaczego Przypadek Najgorszy Jest Dominujący
Systemy muszą obsługiwać przypadek najgorszy. Zapytanie bazy danych, które średnio trwa 10 ms, ale czasami trwa 60 sekund, powoduje widoczną dla użytkownika awarię. Inżynierowie projektują granice dla przypadku najgorszego, aby wydajność pozostała przewidywalna niezależnie od wejścia. Analiza przypadku średniego ma wartość w warunkach probabilistycznych, ale analiza przypadku najgorszego daje gwarancje.
Analiza Przypadków Wyszukiwania Binarnego
Wyszukiwanie binarne działa tylko na posortowanych tablicach. Na każdym kroku: porównaj cel z elementem w środku. Jeśli cel równa się środkowemu elementowi, zwróć go. Jeśli cel jest mniejszy, powtórz na lewej połowie. Jeśli większy, powtórz na prawej połowie.
Każde porównanie eliminuje połowę pozostałych kandydatów.
Wzrost Pamięci & Kompromisy Czas-Pamięć
Liczenie Pamięci, a Nie Operacji
Złożoność czasowa mierzy liczbę operacji, które wykonuje algorytm. Złożoność pamięciowa mierzy dodatkową pamięć, którą przydziela poza swoim wejściem. Oba mają znaczenie w systemach produkcyjnych: szybki algorytm, który przydziela O(N²) pamięci, wyczerpie serwer.
O(1) pamięć: stała dodatkowa pamięć niezależnie od N. Sortowanie w miejscu (np. sortowanie przez wstawianie) zamienia elementy w oryginalnej tablicy. Używa garstki zmiennych tymczasowych — O(1) niezależnie od wielkości tablicy.
O(N) pamięć: pamięć proporcjonalna do rozmiaru wejścia. Utworzenie kopii tablicy N-elementowej wymaga N miejsc. Budowanie zestawu haszowania ze listy N ciągów przechowuje do N wpisów.
O(N²) pamięć: pamięć proporcjonalna do N². Budowanie macierzy sąsiedztwa N×N dla grafu z N wierzchołkami wymaga N² komórek. Przy N = 10 000 wierzchołków to 10^8 wpisów — setki megabajtów dla prostej siatki boolowskiej.
Kompromisy Czas-Pamięć
Jeden z podstawowych posunięć w projektowaniu algorytmów: wymiana przestrzeni na czas lub czasu na przestrzeń.
Tabele haszowane używają O(N) dodatkowej przestrzeni, aby osiągnąć wyszukiwanie O(1). Bez tabeli haszowania skanowanie listy osiąga wyszukiwanie O(N) z O(1) dodatkową przestrzenią. Tabela haszowania płaci pamięcią, aby kupić szybkość.
Memoizacja przechowuje wcześniej obliczone wyniki (O(N) lub więcej przestrzeni), aby uniknąć ich przeobliczania. Rekurencyjna sekwencja Fibonacciego bez memoizacji przebiega w O(2^N) czasu. Z memoizacją: O(N) czasu i O(N) przestrzeni. Inwestycja w przestrzeń zmniejsza czas wykładniczo.
Słownik Haszowany vs Lista Posortowana
Porównaj dwie strategie liczenia występowań słów w dokumencie N słów:
Strategia A: słownik (mapa haszowana). Wstaw każde słowo; zwiększ jego licznik.
Strategia B: utrzymuj posortowaną listę widzianych słów; użyj wyszukiwania binarnego, aby sprawdzić przynależność przed wstawieniem.
Analiza Amortyzowana: Rozkładanie Kosztu
Gdy Okazjonalny Koszt Nie Niszczy Średniej Wydajności
Niektóre operacje są okazjonalnie kosztowne, ale tanie średnio w sekwencji. Analiza amortyzowana oblicza średni koszt na operację w całej sekwencji — nie koszt najgorszego przypadku jednej operacji.
Tablica dynamiczna (lista Pythona, ArrayList Java): zaczyna się z pojemnością 1. Gdy jest pełna, podwaja pojemność. Podwajanie kopiuje wszystkie istniejące elementy: O(N) pracy na jedno dołączenie. Ale podwojenia są rzadkie. Po N całkowitych dołączeniach, ile całkowitych operacji kopiowania miało miejsce?
Podwojenia mają miejsce przy rozmiarach 1, 2, 4, 8, ..., N/2. Liczby kopii: 1 + 2 + 4 + ... + N/2. To jest szereg geometryczny sumujący się do N − 1 całkowitych kopii we wszystkich N dołączeniach. Średnia liczba kopii na dołączenie: (N − 1) / N < 1, więc O(1) amortyzowane na dołączenie pomimo O(N) kosztu najgorszego przypadku na podwojenie.
Dlaczego Analiza Amortyzowana Jest Ważna
System, który okazjonalnie wstrzymuje się, aby zmienić rozmiar, przeprowadzić nową równowagę lub spakować strukturę, może wydawać się mieć niepokojące operacje poszczególnych przypadków najgorszych. Analiza amortyzowana ujawnia, że alarm jest fałszywy: rzadkie kosztowne zdarzenia są opłacone przez wiele tanich. Zrozumienie amortyzowanego kosztu zapobiega przeinżynieryzowaniu: dodawanie złożoności, aby uniknąć rzadkiej operacji O(N), która przyczynia się tylko O(1) amortyzowane, to strata pracy.
Idąc głębiej: kurs unhamming stosuje analizę złożoności do rzeczywistych wad w oprogramowaniu produkcyjnym. Patrz Brakujący Rozdział: Złożoność Algorytmiczna & MOAD-0001: Wada Osadowa.
Wstaw do Tabeli Haszowanej w Amortyzowany Sposób
Tabela haszowana zaczyna się pusta i podwaja pojemność, gdy współczynnik obciążenia przekracza 0,75. Wstawienie 1000 elementów powoduje dokładnie 10 podwojeń przy pojemnościach 1, 2, 4, 8, 16, 32, 64, 128, 256, 512.