🚀 go-pugleaf

Łukasz Rekucki wrote:
>> Co jest w ogólności kłamstwem. Choć w realnych sytuacjach jest OK (choć
>> w realnych sytuacjach można by formalnie poprawnie napisać że dostęp do
>> dowolnego elementu do realnej listy to O(1) tylko stała czasowa duża :)
>>   (Pamięć komputerów jest ograniczona przez stałą, przeszukanie jest
>> jest więc formalnie O(1) -- oczywiście mało to przydatne do
>> czegokolwiek, ale formalnie jest OK. :) )
> Nie, nie można by, bo zależy on od ilości elementów w tej liście.

I co z tego? Jest zawsze ograniczony z góry przez stałą. Przeczytaj 
sobie definicję zapisu O(x).

> I
> nie jest to formalnie ok, bo poprostu liczysz zupełnie coś innego.

Jest formalnie ok. Mało przydatne, ale OK.

> 
>> Wszystkie te O(1) działają tylko i wyłącznie dzięki temu, że pamięć jest
>> skończona, więc długość reprezentacji dowolnego indeksu / hasha itp jest
>> twardo ograniczona z góry niewielką stałą (w dzisiejszych czasach stałą
>> to jest 64).
> Prawię, 2**64, to tylko 1TB 

Ależ skąd. To 16EB -- Pomylileś się "jedynie" 2**24 krotnie.

>- w linux'ie spokojnie możesz mieć 4TB
> pamięci wirtualnej.

Nie szkodzi. To i tak 2**22 razy mniej niż limit.


>> Bo tak na prawdę to zarówno odwołanie do tablicy hashującej czy nawet do
>> dowlonej pozycji w zwykłej tablicy to ma koszt nie O(1) tylko O(log n).
>> Bo nie ma cudów i zapis dowolnego indeksu do struktury długości n musi
>> mieć zająć log n. A że sięgnięcie pod dany indeks w większości
>> przypadków wymaga "obejrzenia" całości jego zapisu to jest ograniczone z
>> dołu przez O(log n).
> 
> Niby masz rację, ale po drodze zmieniasz model obliczeń. Długość
> liczby na takim przyziemnym komputerze jak mój jest stała, a procesor
> wykonuję na niej operację w jednym albo kilku taktach - niezależnie od
> jej wartości. Długość struktury zupełnie go jakoś nie obchodzi.

Oczywiście, że go obchodzi. Dłuższa się nie zmieści. To dosyć kluczowe 
ograniczenie.

> 
>> W dzisiejszych komputerach korzystamy z tego, że podstawa tego log jest
>> duża (2**32 lub 2**64) i dlatego w praktyce zwija się to do O(1).
> NIE, NIE, NIE - Dla dowolnego C i dowolnej funkcji stałej g, Istnieje
> n, t. że log_C(n) > g(n), więc nigdy log_C(n) nie będzie O(1). Nigdy.
> To są dwie różne klasy funkcji.
> 
> Powodem nie jest jakieś *magiczne* oszacowanie, czy zwijanie się,
> tylko model obliczeń. Poprostu mnie nie interesuję ile kosztują
> operację na liczbach!
> 
> Mam:
>  1) pamięć RAM o stałym czasie dostępu
>  2) Maszynę, która umie wykonywać arytmetykę na liczbach w czasie
> stałym.
>  I pytam się jaka jest zależność ilości takich operacji od ilości
> danych?
> 
> To nie jest model uniwersalny, ale się tutaj sprawdza.

To się robi trochę inaczej. Przyjmuje się nie jakąś jednostkę czasu, 
tylko liczbę operacji określonych typów -- wtedy się zgadza i nie zależy 
od wielkości pamięci.


>>> Oczywiście można czepiać się, że czasami w przypadku kilku elementów o 2
>>> takich samych kluczach będzie trzeba wykonać jakąś dodatkową operacje,
>>> jednak w porównaniu z złożonością liniową O(n) dla większej ilości
>>> elementów jest to na tyle nieistotne, że przyjmuje się, że złożoność
>>> jest O(1), a nie np. O(1.3)
>> Jak już inni napisali, O(1) == O(1.3) == O(103453123)
>>
>> Nawet i przy rozsądnych założeniach można mieć pecha i dostać O(n).
>>
>> To O(1) o jakim pisze Cormen to koszt zamortyzowany
> 
> Nie. Co ma wyszukanie do amortyzacji!

To, że łączny koszt wyszukań wszystkich elementów jest ograniczony z 
góry liniowo.

> Wikipedia to może nie jest
> najlepsze źródło, ale tu akurat jest ok:
>

Nie musisz mnie tego uczyć. Zamortyzowany znaczy średni po wszystkich 
wyszukiwaniach.

> Sensowne założenia ~ średni przypadek.

Ale stwierdzenie stały koszt zamortyzowany jest lepsze niż średni koszt 
stały, bo nie bardzo wiadomo co to czas średni -- średnia po czym liczona?

pzdr
\SK

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