@Shalom
Myślę w małej skali, bo problemy informatyczne są w małej skali. W praktyce nigdy nie rozważa się skalowania do nieskończoności. Jak robisz, nie wiem, serwis internetowy, to myślisz o tym, by mógł obsłużyć sto, tysiąc, milion, miliard jednoczesnych użytkowników, ale na tym się zatrzymujesz. Nie myślisz co będzie dla tryliona na przykład, bo to w praktyce bez sensu.
A to moje O(n^(G_64))
faktycznie będzie znikome w porównaniu do O(2^n)
dla pewnych wartości n
, ale te wartości są… nie do opisania ogromne. Nawet gdyby to było samo O(1)
(o jak fajnie, złożoność stała!), tylko ze stałą G_64
. Bo ta liczba wyżyna mózg na drugą stronę przy próbie zrozumienia, jaka jest wielka. Liczba możliwych uporządkowań cząstek elementarnych we Wszechświecie nawet nie zaczyna się do niej zbliżać.
No, kilkadziesiąt lat temu też tak niektórzy narzekali że po co tyle kasy idzie na badania nad komputerami skoro zajmują całe pietra a liczą wolniej niz 4-latek. A jednak troche od tego czasu sie rozwinęło.
To jednak zupełnie inny kaliber problemu. Nawet jakbyśmy mówili o tym algorytmie ze złożonością stałą, to samo przegonienie licznika od zera do G₆₄ by wymagało więcej energii niż ma cały nasz Wszechświat. To nie jest skala problemów inżynieryjnych, tylko takich, dla których musielibyśmy budować komputer z czego innego niż materia gdzie indziej niż u nas we Wszechświecie.
Dość powiedzieć, że jeśli oznaczymy sobie przez g googleplex, czyli 10^(10^100) i będziemy pisać g^g^g^g^g…, to nawet jeśli te g będą rozmiarów pojedynczych atomów, to braknie nam tychże w całym obserwowalnym wszechświecie by zapisać liczbę Grahama.
Dlaczego więc wziąłem taką ogromną liczbę? Bo to jest rozwiązanie innego matematycznego problemu, tw. Grahama-Rothschilda. I powinno stanowić pewną przestrogę co do tego, co w matematyce jest satysfakcjonującym rozwiązaniem.
EDYCJA:
Dosyć plastyczne przedstawienie tego, jak bardzo absurdalnie wielka jest ta liczba: http://waitbutwhy.com/2014/11/1000000-grahams-number.html