🚀 go-pugleaf

Łukasz Rekucki wrote:
> Uważam, że dalsza dyskusja z tobą nie ma sensu, bo mylisz pojęcia
> matematyczne i ich zastosowanie do analizy asymptotycznej złożoności
> algorytmów z jakimiś swoimi wyobrażeniami.

Whatever. Chciałeś powiedzieć, że nie masz argumentów. Rozumiem.
Przy okazji musiałeś zacytować cały post wraz z sygnaturką i odpisać nad 
cytatem.

Przypomnę tylko kilka faktów...
1. Pamięć każdego komputera, w odróżnieniu od maszyny Tuninga czy 
maszyny RAM, *jest* ograniczona.
2. Jeśli pamięć jest ograniczona to wszelkie obliczenia albo zakończą 
się albo zapętlą się w czasie 2^M gdzie M to wielkość pamięci w bitach.
3. Czas ten dla realnych komputerów jest oczywiście absurdalnie wielki, 
więc takiego podejścia się nie stosuje, bo nie ma praktycznego sensu. 
Dlatego napisałem: "oczywiście mało to przydatne do czegokolwiek, ale 
formalnie jest OK.". Niezależnie od przyjętego formalizmu *można* tak 
powiedzieć, choćbyś tupał i zatykał uszy.
3a. Algorytm sprawdzania czy wśród pierwszych C (C stałe) elementów 
tablicy (czy listy) nie ma wybroanego elementu X, realizuje się w 
koszcie stałym. Prawda?
4. Jako bardziej użytecznego formalizmu używa się (abstrakcyjnej) 
maszyny RAM której cechą charakerycztyczną nie tylko jest nieskończona 
liczba komórek pamięci, ale nieskończona pojemność każdej komórki. W tym 
modelu rozpatruje się normalnie używane algorytmy, a nie w modelu 
realnego komputera który jest skończony.
5. Alternatywnie do 4 koszt liczy się w liczbie "operacji dominujących" 
koszt pozosytałych uznając za zerowy.


Na marginesie:
Co do tablic haszujących to założenie kosztu stałego opiera się na 
założeniu że wyliczenie hasha ma koszt stały -- i z tym założeniem też 
trzeba sobie poradzić.

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