Każda klasa złożoności rysuje krzywą
Wykreśl koszt względem rozmiaru wejścia
Umieść rozmiar wejścia N na osi x. Umieść koszt (operacje, czas) na osi y. Każda klasa złożoności tworzy odrębną krzywą. Tempo wzrostu algorytmu można rozpoznać po kształcie jego krzywej wydajności.
O(1) — płaska linia pozioma. Funkcja f(N) = 1. Brak nachylenia. Koszt nigdy się nie zmienia niezależnie od N. Wyszukiwanie w tablicy haszującej: niezależnie od tego, czy tablica zawiera 10 czy 10 000 000 elementów, jedno obliczenie haszowania przeskakuje do właściwego kubełka.
O(log N) — łagodnie rosnąca krzywa, nachylenie malejące. Przy N = 1 000 000: koszt ≈ 20 operacji. Krzywa rośnie stromo przy małym N, a następnie się spłaszcza. Każde podwojenie N dodaje dokładnie jedną jednostkę kosztu.
O(N) — linia prosta diagonalna. Nachylenie = 1 (w sensie asymptotycznym). Koszt rośnie w tym samym tempie co N. Jeśli N się potraja, koszt się potraja.
O(N log N) — bardziej stroma diagonalna z lekkim wyginięciem w górę. Siedzi powyżej O(N) ale poniżej O(N²). Czynnik log dodaje powoli rosnący mnożnik do liniowego nachylenia.
O(N²) — parabola otwierająca się w górę. Nachylenie rośnie wraz z N. Przy N = 10: koszt = 100. Przy N = 100: koszt = 10 000. Przy N = 1 000: koszt = 1 000 000.
Rosnąca luka
Stosunek O(N²) / O(N) = N. Luka między parabolą a diagonalną rozszerza się wraz ze wzrostem N. Przy N = 10: luka 10×. Przy N = 100: luka 100×. Przy N = 1 000: luka 1 000×. Przy N = 50 000: luka 50 000×. Luka równa się N — zawsze.
Obliczanie luki skali
Duży graf zależności zawiera 50 000 pakietów (N = 50 000). Jeden algorytm działa w czasie O(N). Drugi działa w O(N²). Przy tym N stosunek O(N²)/O(N) = N = 50 000.
Dzielenie segmentu linii na pół
Wyszukiwanie binarne jako powtarzające się połowienie
Posortowana tablica N elementów tworzy segment linii o długości N. Wyszukiwanie binarne wielokrotnie dzieli ten segment:
1. Wskaż na środek pozostałego segmentu.
2. Jeśli cel < środek: prawa połowa znika. Powtórz na lewej połowie.
3. Jeśli cel > środek: lewa połowa znika. Powtórz na prawej połowie.
4. Jeśli cel = środek: gotowe.
Po k połowieniach, pozostały segment ma długość N / 2^k. Wyszukiwanie kończy się, gdy ta długość równa się 1:
N / 2^k = 1 → 2^k = N → k = log₂N
Zatem wyszukiwanie binarne na N elementach wymaga co najwyżej log₂N porównań.
Połowienie & podwojenie: dwie strony tej samej krzywej
Połowienie i podwojenie są geometrycznymi odwrotnościami. Krzywa wykładnicza 2^k i krzywa logarytmiczna log₂N są odbiciami każdej drugiej na linii y = x.
Rozważ składanie papieru: arkusz zaczyna się od grubości 0,1 mm. Każde złożenie podwaja grubość. Po 42 złożeniach: 0,1 mm × 2^42 ≈ 439 804 km — poza księżyc (384 400 km). Wyszukiwanie binarne działa w odwrotnym kierunku: zacznij od N elementów, każdy krok zmniejsza o połowę liczbę, osiągnij 1 element w log₂N krokach.
Geometria: połowienie jest operacją samopodobną. Każde połowienie tworzy dwie połowy, które wyglądają identycznie w strukturze do całości. Rekursja i logarytmy dzielą to samopodobieństwo.
Porównania i podwojenia
Posortowana tablica zawiera 1 048 576 elementów. Uwaga: 1 048 576 = 2^20.
Funkcja haszująca jako geometryczne mapowanie
Funkcja haszująca jako funkcja
Tablica haszująca mapuje klucz do kubełka za pomocą funkcji haszującej:
bucket = hash(key) mod table_size
To jest funkcja w ścisłym sensie matematycznym: mapuje dziedzinę (wszystkie możliwe klucze) do zakresu (indeksy kubełków od 0 do table_size − 1). Obraz geometryczny: klucze zajmują jedną przestrzeń; kubełki zajmują inną. Funkcja haszująca projektuje klucze na indeksy kubełków.
Wyszukiwanie O(1) — bezpośredni skok, brak wyszukiwania. Funkcja haszująca oblicza indeks kubełka w stałym czasie. Przeskocz bezpośrednio do tego kubełka. Brak traversu, brak pętli porównania.
Współczynnik obciążenia. Przy współczynniku obciążenia 0,75, 75% kubełków zawiera co najmniej jeden element. Powyżej ~0,9 kolizje się zwiększają: dwa klucze haszują do tego samego kubełka, tworząc łańcuch elementów wewnątrz tego kubełka. Wyszukiwanie w długim łańcuchu pogarsza się do O(N) w najgorszym przypadku.
Jakość dystrybucji jako geometria
Dobrze rozpowszechniona funkcja haszująca rozprzestrzenia klucze równomiernie na wszystkich kubełkach. Geometrycznie: zakres funkcji pokrywa swój kodomenę równomiernie. Każdy kubełek otrzymuje około N / table_size kluczy.
Słaba funkcja haszująca skupia klucze w kilku kubełkach. Geometrycznie: zakres funkcji kurczy się do podzbioru kodomain — większość kluczy mapuje do tych samych kilku punktów. Pozostałe kubełki pozostają puste.
Połączenie z MOAD-0001
Zastąpienie listy zbiorem naprawia MOAD-0001, ponieważ zbiór używa wewnętrznie tablicy haszującej. Skan listy O(N) → wyszukiwanie tablicy haszującej O(1). Geometrycznie: liniowy traversal sekwencji przekształca się w bezpośrednią projekcję za pośrednictwem funkcji. Sekwencja znika; funkcja ją zastępuje.
Analiza słabo rozpowszechnionej funkcji haszującej
Tablica haszująca ma 1 000 kubełków i 900 elementów (współczynnik obciążenia 0,9). Słaba funkcja haszująca wysyła 500 z tych elementów do tego samego kubełka.