🚀 go-pugleaf

> 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
nie jest to formalnie ok, bo poprostu liczysz zupełnie coś innego.

>
> 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 - w linux'ie spokojnie możesz mieć 4TB
pamięci wirtualnej.

> 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.

> 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.

> > 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! Wikipedia to może nie jest
najlepsze źródło, ale tu akurat jest ok:

http://en.wikipedia.org/wiki/Best,_worst_and_average_case

Sensowne założenia ~ średni przypadek.

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