🚀 go-pugleaf

Jako że grupę czytują również "dzieci" (np. takie co to właśnie uczą się 
o złożoności asymptotycznej, itd). to rozwinę.

Żeby w ogóle mówić o (nietrywalnej) złożoności asymptotycznej (czyli dla 
rozmiaru danych dążącego do nieskończoności) realizowany (abstrakcyjny) 
algorytm nie może mieć ograniczenia na wielkość danych. Jeśli wielkość 
danych jest ograniczona (przez stałą), to mówienie o złożoności dla 
dowolnie wielkich danych jest bez sensu, w najlepszym razie mamy 
przypadek trywialny, czyli złożoność (asymptotycznie) stałą -- O(1).

Należy pamiętać że jeśli gdzies jest mowa o stałej to to może byc 1, 2, 
3, 100, 0.000001, ale także 2**35, albo i 2**(2**35) albo i dowolnie gorzej.

Jeśli już przejdziemy do dowolnie wielkich danych to złożoność różnych 
teoretycznie prostych algorytmów będzie różna w zależności od użytego 
modelu. Np. banalne odwołanie do k-tego indeksu w zwykłej tablicy w 
zależności od modelu będzie miało złożoność O(1), O(log n) albo i O(n) 
lub gorzej, to ostatnie dotyczy zwykłej maszyny Turinga choćby i z 
wieloma taśmami -- bo w niej dostęp jest sekwencyjny i już. Przy czym w 
modelach o dostępie swobodnym może być zarówno O(log n) jak i O(1) 
zależnie od tego czy mamy model z ograniczonymi rejestrami[*] (mamy 
alfabet symboli rejestrowych i nieskończenie wiele rejestrów) czy też, 
jam maszyna RAM z nieograniczonymi rejestrami (każda "komórka pamięci" 
tej abstrakcyjnej maszyny przechowuje dowolną liczbę naturalną, czyli ma 
nieograniczoną pojemność i tych komórek znowu jest nieskończenie wiele).
Pozostaje jeszcze liczenie liczby tzw. operacji dominujących, np. liczby 
porównań, kopiowań, dostępów do pamięci itd. Ale to również musi być 
zanużone w jakimś modelu abstrakcyjnej maszyny. Oczywiście, jeśli np. 
będziemy liczyli liczbę kopiowań przechowywanych danych, czy np. liczę 
odwołań do tablicy to można mieć trywialnie koszt O(1), ale to i w wielu 
opeacjach drzewiastych liczba kopiowań na wstawienie jest stała (równa 
1). Zatem z operacjami dominującymi trzeba uważać -- muszą być 
rzeczywiście dominujące.

[*] ograniczone są wszystkie rejestry poza jednym -- trzeba jakoś 
zaindeksować dowolny rejestr.


Zatem... w zależności od tego co nas interesuje stosujemy różne modele. 
Ale nie wolno zapomnieć o powyższym (różnych złożonościach tego samego 
rozwiązania). Różnice złożoności między różnymi modelami (Turing 
complete, nie wliczamy tu zliczania operaci dominujących bo to trochę co 
innego) mogą być duże, ale też zwykle nie przekraczają O(n**3) a i też 
gwarantuje się że ogólna klasa O(wielomian(n)) czy O(2**wielomian(n)) 
itd jest zachowana. Wynika to z tego, że każdy z tych modeli może 
zasymulować inny z narzutem wielomianowym (i ten wielomian jest 
konkretny, zwykle nie gorszy niż 3 stopnia).


Co do samego hashowania i jego liniowości nawet w modelu RAM 
(nieskończenie wiele nieograniczonych rejestrów z dostępem swobodnym) to 
jest jeszcze problem zasadniczy (o którym napisałem na górze) -- funkcja 
mieszająca ma po pierwsze bardzo często stałej wielkości wyniki (dotyczy 
zdecydowanej większości realnie używanych hashy, czy to różnych prostych 
xor/shift/mod czy crc, czy md4, czy md5 czy sha1, itd) więc dla 
odpowiednio dużych danych przestaje działać (co z tego, że mamy 2**36 
pozycji w tablicy skoro użyty hash crc32 da 2**32 różnych wyników). Po 
drugie nawet na maszynie RAM z dodatkami (typu operacje arytmetyczne i 
bitowe a nie tylko inkrementacja) typowy sensowny hash liczy się w 
czasie liniowo zależnym od wielkości hashowanych danych a nie w czasie 
stałym.

W innych modelach maszyn niż RAM-podobne (nieskończenie wiele 
nieograniczonych rejestrów) w ogóle nie ma co mówić o stałym koszcie 
liczenia hasha. No chyba że używamy zliczania operacji dominujących i za 
taką uznajemy policzenie hasha, ale to jest masło maślane.


Do tego nie wolno zapomnieć, że w dzisiejszych rzeczywistych komputerach 
(poza drobnymi komputerkami wbudowanymi (embedded)) dostęp do pamięci 
nie jest jednolity -- nawet bez swapowania różnice w czasie dostępu 
sięgają 3 rzędów wielkości (do ok. 1000 razy) i zależą nie tylko od 
trafień w cache ale np. dostęp sekwencyjny do większych bloków średnio 
bywa kilkanaście-kilkadziesiąt razy szybszy niż stricte swobodny. Ale to 
już temat na osobną bajkę.

\SK

-- 
"Never underestimate the power of human stupidity" -- L. Lang
-- 
http://www.tajga.org -- (some photos from my travels)