Když budu mít paměť technicky realizovanou jako matici buněk adresovaných adresními vodiči, tak časová náročnost přístupu je O(1).
Myslim, ze jsi neporozumel tomu, co rikam. Pokud mame konkretni mnozstvi pameti, N, pak ano, casova narocnost pristupu do takove pameti je O(1) (pro vsechny algoritmy a jejich vstupy ktere mohou bezet s pameti do velikosti N).
Jenze, problem je v tom, ze takove tvrzeni plati pro vsechny pameti. Napriklad paskova pamet o velikosti N bajtu je take pristupna v O(1), pokud uvazujeme konkretni program a vstup, ktery spotrebovava maximalne N bajtu pameti. Proste, jelikoz je N pevne, muzeme ho schovat do te konstanty.
A bude to tak fungovat bez ohledu na to, jak je ta paměť velká.
Ale pokud budeme uvazovat o sirsi mnozine algoritmu a vstupu, treba mnozine vstupu libovolne velkych, musime i pripustit, ze je muzeme poustet na strojich s libovolne velkou RAM. Tedy N nebude omezene, doba pristupu do pameti na tech strojich take nebude omezena, bude rust O(log N).
Proto nema smysl nad takovou mnozinou algoritmu a vstupu uvazovat o stroji, ktery pristupuje k pameti v O(1) pro libovolne N - takovy stroj je jen teoreticky konstrukt.
OK, asi jsem dnes nějaký přibržděný nebo jsem příliš prakticky orientovaný, když to stále nechápu, ale já ještě nepotkal počítač s neomezenou pamětí. Tak proč by to někoho v praxi mělo trápit? Mimochodem, pro pásku to přece pravda není, protože ji musím převíjet. Buď ji považuji za paměť s náhodným přístupem, to když mohu dobu převíjení vzhledem k rychlosti provádění operací zanedbat, pak má složitost
O(1), nebo nemohu, a pak má složitost (obecně)
O(
f(n)).
Taky je mi jasné, že tato rozdílná složitost bude mít dopad na celkovou složitost algoritmů na takových pamětech postavených, tedy výhodnost algoritmů, z nichž jeden provádí méně přesunů dat, ale za to na dálku, v porovnání s algoritmem, přesunující sice sousední data, ale vícekrát, se může otočit, vyrovnat, či se aspoň přiblíží jeden k druhému.
Ale to už se dostáváme na příliš konkrétní úroveň. Nelze prostě říci, že složitost přístupu k paměti je taková a taková, protože cache. Teď právě mi na stole poblikává jedna deska, pro níž něco vyvíjím, a rozhodně tam žádná cache není.
Takže co tu vlastně porovnáváte? Nemohu se zbavit dojmu, že jablka s hruškami, podle toho, jaká vlastnost vychází lépe.
A pokud jde o ten odkazovaný článek, tak je to opravdu tak napůl esoterická záležitost, protože se snaží nás přesvědčit, že chceme-li posuzovat časovou složitost co nejobecněji, tak musíme předpokládat sice konečná, ale libovolně rozsáhlá data, na nichž ukazuje, že je obecně nelze obsloužit v konstantním čase z ryze fyzikálních důvodů (jen jsem čekal, kdy tam začne vytahovat holografický princip z teorie strun).
To je sice roztomilé, ale jen jako taková kratochvilná teoretická onanie. Protože v praxi při porovnávání algoritmů předpokládám nikoliv "sice konečné, avšak libovolně rozsáhlé" paměti, ale jeden a ten samý konkrétní stroj.
Takže pokud by mi podobný rozumbrada začal opravovat mé odhady řka, že přístup k paměti má přece složitost
O(√
n), pousmál bych se, poplácal bych ho po tvářičce a popřáv mu mnoho radosti při onaniích nad řešením otázek, kolik andělů se vejde na povrch horizontu událostí černé díry, bych ho kopnul do...
998 Odpovědí
233532 Zhlédnutí