🚀 go-pugleaf

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.

On Jan 18, 12:21 pm, Sebastian Kaliszewski
<s.bez_sp...@remove.this.informa.and.that.pl> wrote:
> Psujesz polskie literki.
>
> Łukasz Rekucki wrote:
> > On Jan 15, 12:48 pm, Sebastian Kaliszewski
> > <s.bez_sp...@remove.this.informa.and.that.pl> wrote:
> >> 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).
> > Nie jest ograniczony przez stałą,
>
> Oczywiście że jest. Ba, komputer stojący na twoim biurku można spokojnie
> przedstawić jako automat skończony (trochę duży, ale skończony).
>
> > bo model obliczeń o którym
> > rozmawiamy, nie ma takich ograniczeń jak pamięć!
>
> Oczywiście że ma.
>
> > Definicja klas o(x), O
> > (x) i theta(x) to już w ogóle nie widzą co to jest "pamięć"
>
> Oczywiście że wiedzą. Liczba symboli nie blank na taśmie maszyny Turinga
> to jest pamięć.
>
> >. Jaki jest
> > sens notacji granicznej do nieskończoności, jeśli ograniczasz z góry
> > argumenty ?! żaden.
>
> Dlatego nie należy ich ograniczać. Ale wtedy indeks tablicy też nie jest
> ograniczony. Jeśli ograniczyłeś długość indeksów do stałej to
> ograniczyłeś również do stałej wielkość tablicy.
>
> >>> I
> >>> nie jest to formalnie ok, bo poprostu liczysz zupe nie co innego.
> >> Jest formalnie ok. Ma o przydatne, ale OK.
> > Nie w  tym modelu obliczeń. W innym może tak, ale nie w tym.
>
> W tym, w tym.
>
> >>>> 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.
> > Ok, pomyliłem się.
>
> >>> - w linux'ie spokojnie mo esz mie 4TB
> >>> pami ci wirtualnej.
> >> Nie szkodzi. To i tak 2**22 razy mniej ni limit.
> > Niż 2**64 taj, ale do tego nie trzeba mieć architektury 64-bitowej.
> > Jeśli masz tylko 32-bitowe adresy, to każdy proces jest ograniczony do
> > 4GB, ale cały może alokować więcej. Technika jest prosta - należy
> > używać tablic wielopoziomowych.
>
> Czyli wydłużyć indeksy. Jak używasz "tablicy wielopoziomowej" to dla
> nieograniczonej pamięci trzeba w sposób nieograniczony zwiększyć liczbę
> poziomów -- i z tablicy mamy drzewo :)
>
> >>>> 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.
> > Twój komputer ma widać dużo zmartwień. Co nie zmienia faktu, że 1 +1
> > działa tak samo szybko jak 10000 + 10000.
>
> ale nie tak samo szybko jak
> 12391823712345189374918743198374+1290348571028761782645245412454.
>
> BTW rozszerzenie 32bity -> 64bit nie jest za darmo, procesor 32bit
> wykonany w dokładnie tym samym procesie będzie kilka procent szybszy.
>
>
>
>
>
> >>>> 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.
> > Inaczej, czyli tak jak napisałem. Interesuje mnie ilość dostępów do
> > pamięci i operacji arytmetyki.
>
> Nie. Ilość dostępów do pamięci rośnie (logarytmicznie) wraz wielkością
> adresowanej pamięci.
>
> Przyjmuje się liczbę odwołań (być może złożonych) pod podany adres
>
>
>
>
>
>
>
> >>>>> 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.
> > I co ma to wspólnego z amortyzacją ? Koszt znalezienia pojedyńczego
> > elementu, też się szacuję z góry przez ilość elementów. I co nagle do
> > tego mają wszystkie elementy?
>
> >>> 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.(
> > Nie. Zamortyzowany znaczy średni w ciągu N operacji np. N razy znajdź
> > liczbę 8. Jeśli 8 było na końcu listy kollzji długości n/2, to
> > jednostkowy koszt będzie O(n) i zamortyzowany też będzie O(n). Jeśli
> > bardzo się upierasz przy znajdowaniu wszystkich, to wystarczy wziąć
> > tablicę z K elementami, gdzie wszystkie są w kolizji. Wyszukanie ich
> > wszystkich zajmię ci ~ K^2.
>
> >>> 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?
> > średni koszt = koszt w średnim przypadku.
>
> Co to jest średni przypadek?
>
> > Bardziej po polsku pewnie by
> > było "typowym" przypadku, ale tak już jakoś jest. To co jest typowym
> > przypadkiem oczywiście jest bardzo względne. Dlatego w Cormenie jest
> > "sensowne założenia"!
>
> pzdr
> \SK
> --
> "Never underestimate the power of human stupidity" -- L. Lang
> --http://www.tajga.org-- (some photos from my travels)