pricom jeho otazka je uplne jasna.
Právěže není. Wasper na to upozorňuje taky. Nejsme na webu o matematice, ale na webu o počítačích. Tazatel neumí/nechce konkretizovat zadání. Nevíme, co je cílem, nevíme, jaké jsou omezující podmínky, nevíme, co je k dispozici.
Podstata je, kolik taktů je potřeba na výpočet. Resp. kolik taktů navíc oproti N je potřeba pro výpočet N+1. A zde záleží na tom, jaké aritmetické operace se budou používat, s jakými datovými typy, na jaké architektuře. "...operací v nejhlubším cyklu" - to chápu jako úvahu o vnořených cyklech (for, while), ale tak to nemusí nutně být.
Tazatel se ptal na asymptotickou složitost, ta je alespoň v mé sociální bublině (kolem matfyzu) definována dost jasně, základní operace s čísly (sčítání, násobení, dělení; odmocnina už je trochu sporná, ale tazateli ji stačí vypočítat jednou na začátku) jsou konstantní pokud není uvedeno/nelze předpokládat že je to jinak a nějaké počty taktů se neřeší, protože to jen násobí konstantou a v běžně používané "big-O notation" se konstanty zanedbávají.
Tady je ale problém v tom, že tazatel si musí vyjasnit, vzhledem k čemu složitost chápe. Složitost se většinou uvádí vzhledem k bitové velikosti vstupu: zatímco i roste lineárně, jeho bitová velikost roste logaritmicky. Takže člověk by tady naivně řekl že to má lineární složitost (uděláme lineárně kroků vzhledem k i - testujeme nějaká čísla od 0 do i), ale uvádí se, že to má 2^n, protože pro představu třeba pro i=1024 uděláme 1024 kroků, ale „velikost vstupu“ je jenom 10 (bitů), pro velikost vstupu 20 už uděláme milion kroků atd.
Odpovědi na jeho dotazy vzhledem k i by tedy byly: O(i), O(sqrt(i)), O(něco něco
https://en.wikipedia.org/wiki/Prime-counting_function, takže asi log(i), ale záleží jak si prvočísla generuje a jak je má uložena), a z hlediska asymptotického je jedno jestli si předpočítá odmocninu nebo počítá i*i (v praxi je samozřejmě nejlepší předpočítat).
Problém tazatelova popisu také je, že je takový celkově zmatený, a motivace (o co mu jde) by taky pomohla.
Pokud by ho tedy zajímala „standardní složitost vzhledem k n“, tak „stačí exponenciálovat výše uvedené“ *, ale problém je, že už možná má na mysli operace s čísly, která nejsou konstantně velká, a tak se nedá použít ten předpoklad, že operace s nimi trvají konstantně dlouho. (v praxi ale ten limit bývá délka čísla v počítači, tedy 64 bitů, a tam se s takhle naivním algoritmem nedostane; pro chytřejší testování prvočíselnosti už to ale problém být začne).
*Pozor, že u manipulace s exponenciálními funkcemi se věci v exponentu chovají jinak než by člověk intuitivně čekal, například O(2^(2n)) není O(2^n) i když O(n) je O(2n), kdysi jsem přesně tohle grandiózně zfailil ve škole.
https://softwareengineering.stackexchange.com/questions/312563/time-complexity-of-2sqrtnhttps://stackoverflow.com/questions/4856107/is-22n-o2n
12 Odpovědí
5212 Zhlédnutí