Szybszy komputer może prawie niczego nie zmienić
Jeżeli algorytm wymaga sprawdzenia około 2^n możliwości, ogromny wzrost mocy sprzętu może dać zaskakująco mały zysk. Komputer tysiąc razy szybszy nie pozwala wtedy zwiększyć n tysiąckrotnie, lecz tylko o około 10, bo 2^10 ≈ 1000. Nawet miliardkrotne przyspieszenie odpowiada zaledwie około 30 dodatkowym elementom. To istota eksplozji kombinatorycznej: liczba przypadków rośnie szybciej, niż sprzęt potrafi ją dogonić. Dlatego w informatyce przełomem bywa nie szybszy procesor, lecz znalezienie algorytmu o zupełnie lepszym tempie wzrostu czasu działania.
Ściana ukryta w wykładniku
Wyobraźmy sobie zadanie, w którym dla n elementów trzeba rozważyć każdy ich podzbiór. Podzbiorów jest 2^n. Dla 20 elementów to nieco ponad milion możliwości, dla 30 — już ponad miliard, a każde zwiększenie n o jeden dokładnie podwaja liczbę przypadków. Właśnie dlatego intuicja z codziennego życia zawodzi: problem nie rośnie „trochę”, lecz mnoży poprzednią pracę przez stały czynnik przy każdym kolejnym elemencie. Podobny mechanizm pojawia się w naiwnych metodach rozwiązywania wielu problemów kombinatorycznych, gdy program próbuje wszystkie konfiguracje zamiast wykorzystywać strukturę zadania.
Co naprawdę daje szybszy procesor
Załóżmy, że stary komputer potrafił w rozsądnym czasie obsłużyć rozmiar n, wykonując około 2^n kroków. Nowa maszyna jest tysiąc razy szybsza. Szukamy więc takiego k, aby 2^(n+k) było najwyżej tysiąc razy większe niż 2^n. To oznacza 2^k ≈ 1000, a więc k ≈ 10. Miliard razy szybsza maszyna daje k ≈ 30. To nie jest pesymistyczna prognoza sprzętowa, lecz czysta własność funkcji wykładniczej: stały mnożnik prędkości zamienia się w stały dodatek do maksymalnego rozmiaru wejścia.
Algorytm może być ważniejszy niż sprzęt
Kontrast z algorytmem wielomianowym jest ogromny. Jeśli czas rośnie przykładowo jak n^3, tysiąckrotne przyspieszenie pozwala w tym samym budżecie czasu zwiększyć n około dziesięciokrotnie, bo 10^3 = 1000. Przy 2^n ten sam mnożnik daje tylko około dziesięciu dodatkowych elementów niezależnie od tego, czy startujemy od n=20, 100 czy 1000. To powód, dla którego teoria złożoności interesuje się przede wszystkim sposobem skalowania wraz z długością wejścia, a nie wyłącznie liczbą sekund na konkretnym komputerze.
Nie każda wykładniczość oznacza porażkę
W praktyce algorytm o wykładniczym najgorszym przypadku może być użyteczny dla małego n albo dzięki strukturze rzeczywistych danych. Można też redukować przestrzeń poszukiwań, stosować heurystyki, programowanie dynamiczne, aproksymację czy parametryzację. Twierdzenie nie brzmi więc „algorytm 2^n nigdy nie działa”, lecz „sam wzrost mocy sprzętu nie usuwa jego fundamentalnego problemu skalowania”. Gdy n ma rosnąć o setki lub tysiące, różnica między 2^n a wielomianem staje się jakościowa.
Dlaczego to zmienia sposób projektowania programów
Wydajność często poprawia się nie przez mikrooptymalizację, lecz przez zmianę modelu rozwiązania. Sortowanie lepszym algorytmem, unikanie pełnej enumeracji, wykorzystanie właściwości grafu czy rozbicie zadania na podproblemy może zmienić wykładnik albo całkowicie zastąpić wzrost wykładniczy wielomianowym. To właśnie w takich sytuacjach „szybszy komputer” i „lepszy algorytm” nie są dwiema wersjami tego samego ulepszenia: druga zmiana może otworzyć skalę problemu, której pierwsza nigdy praktycznie nie osiągnie.
Co mówi nam proste przeliczenie skali
Można to zobaczyć bez żadnych założeń o konkretnej technologii. Jeżeli pewien komputer rozwiązuje problem o koszcie 2^100 w granicznym akceptowalnym czasie, maszyna tysiąc razy szybsza dostaje budżet około 1000·2^100 operacji. Ponieważ 1000 jest bliskie 2^10, nowa granica leży w pobliżu 2^110, czyli rozmiaru 110, a nie 100 000. Nawet poprawa sprzętu o czynnik milion odpowiada tylko około 20 dodatkowym elementom, bo 2^20 to nieco ponad milion. Ten rachunek dobrze oddziela dwie rzeczy często wrzucane do jednego worka: ogromny mnożnik wydajności sprzętu oraz zmianę asymptotycznego tempa wzrostu. Pierwsza przesuwa ścianę, druga może zmienić jej kształt.