🚀 go-pugleaf

wodzik wrote:
> On 2010-01-09 23:24, Stachu 'Dozzie' K. wrote:
> 
>> To ze szkoły powinieneś wiedzieć że to nie do końca daje złożoność O(1).
> 
> Powiedz to moim wykładowcom, albo chociaż by Thomasowi Cormenowi. 
> Cytując z książki "Wprowadzenie do algorytmów":
> -"Przy rozsądnych założeniach można wykazać, że oczekiwany czas 
> wyszukiwania elementu z tablicy z haszowaniem wynosi O(1)."
> czy:
> -"średni czas działania podstawowych operacji słownikowych na tablicy z 
> haszowaniem wynosi O(1)."

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

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


Bo tan ka 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).

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


> 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


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