zložitosť algoritmu

tina.olbreitova

viete mi poradiť podľa čoho píšem zložitosť algoritmu???
mám napr. rovnicu x3(n)2 + x4 bude zložitosť n4???

najprv sa musíš rozhodnúť či chceš rátať časovú alebo pamäťovú zložitosť a potom sa môžeme začať rozprávať o výpočtoch

tina.olbreitova

to som tu zabudla napísať, ja som ale "ťuk". časovú zložitosť

Blekota

to tu čo sa po mimozemšťansky bavite?

dobre, teraz skús napísať algoritmus (lebo pre výraz nemá zmysel počítať časovú zložitosť, tá je vždy konštantná). Ak je teda tým zápisom čo si dala zapísané to čo si myslím a to ako to vypadá

tina.olbreitova

práveže to budem mať v teste a na základe dákeho príkladu podobného typu ako som napísala napísať zložitosť algoritmu - časovú.

aby si mohla rátať časovú zložitosť, musíš si stanoviť nejakú operáciu ktorá bude vyjadrovať základnú časovú zložitosť. Väčšinou sa takouto operáciou bere priradenie, a preto to má zmysel rátať v algoritmoch (kde sú cykly, podmienky..). Vo výraze je časová zložitosť vždy konštantná, lebo pre ľubovolné n získaš výsledok na jeden krok (vypočítaním výrazu). Skús presne napísať ten výraz aj so zadaním (možno to n v zátvorke značí niečo iné ako n v zátvorke

). Ak sú tam nejaké exponenty, alebo indexy čo nie je jasné z tohto zápisu tak radšej naskenuj originál zadanie a daj ako obrázok

tina.olbreitova

to nie je konkrétny príklad, ktorý mám vyriešiť, to je len moje vymyslené zadanie, máme napríklad zložitosti algoritmov pre prácu s maticami napr. pri súčte je to On2

no vidíš, našlo sa kde je pes zakopaný

vymyslela si zlý príklad, a konečne sa (po zadaní skutočného príkladu) dostávame k tomu že zložitosť sa počíta pri algoritmoch.
On2 (lepšie zapísané On^2 aby bolo jasné že dvojka je mocnina) znamená že to má kvadratickú zložitosť. Čiže pri zvýšení n o 2 sa zložitosť zvýši o exponenciálne na 4. Základom je vždy si uvedomiť (alebo napísať) algoritmus z ktorého to buď je hneď vidno alebo si to vyjadríš matematicky. Obávam sa že aj jedno aj druhé môže byť problém, hlavne pre mňa ak to má byť štýlom "doučovania cez diskusné forum"

tina.olbreitova

aj tak dík, snaha sa cení....nuž len sa spoliehať, že ma zajtra na skúške osvieti....

kde študuješ?

neutronmind

Ak f(n) je funkcia udavajuca casovu zlozitost algoritmu v zavislosti od velkosti vstupu n, piseme f(n) = O(g(n)) prave vtedy, ked f(n) <= c.g(n) pre nejaku konstantu c a vsetky n vacsie ako nejake n_0. O(g(n)) je v podstate mnozina funkcii, ktore rastu pomalsie ako g(n). Jednoducho povedane, ak f(n) = O(g(n)), tak graf funkcie g(n) lezi nad grafom funkcie f(n), f(n) je teda zhora ohranicena funkciou g(n). Je to teda nejaky horny odhad rastu funkcie - garantujeme, ze algoritmus s cas.zlozitostou O(g(n)) spravi najviac c.g(n) krokov. Plati teda napr. n^2 = O(n^2), n^42 = O(n^47) atd... Lubovolny polynom stupna k patri do O(n^k).

tina.olbreitova

no nakoniec to dopadlo ok, mali sme len napísať zložitosť pre prácu s maticami - presnejšie skalárny súčin matíc...študujem v ružomberku