Teória výpočtovej zložitosti sa zameriava na klasifikáciu výpočtových problémov podľa ich využitia zdrojov a na vzájomné prepojenie týchto tried. Výpočtový problém je úloha, ktorú rieši počítač. Výpočtový problém je riešiteľný mechanickou aplikáciou matematických krokov, ako je napríklad algoritmus.
Čo myslíš pod pojmom zložitosť algoritmu?
Zložitosť algoritmu je miera množstva času a/alebo priestoru, ktoré algoritmus vyžaduje pre vstup danej veľkosti (n).
Čo je algoritmická zložitosť v dátovej štruktúre?
Algoritmická zložitosť je meradlom toho, ako dlho by algoritmus trval dokončenie pri vstupe s veľkosťou n. Ak má algoritmus škálovať, mal by vypočítať výsledok v konečnom a praktickom časovom limite aj pre veľké hodnoty n. Z tohto dôvodu sa zložitosť počíta asymptoticky, keď sa n blíži k nekonečnu.
Prečo je dôležitá zložitosť algoritmu?
Počítačoví vedci používajú matematické miery zložitosti, ktoré im umožňujú pred napísaním kódu predpovedať, ako rýchlo bude algoritmus bežať a koľko pamäte bude vyžadovať. Takéto predpovede sú dôležitými návodmi pre programátorov, ktorí implementujú a vyberajú algoritmy pre aplikácie v reálnom svete.
Ako sa vypočítava zložitosť algoritmu?
Pre každú slučku zistíme dobu behu bloku v nej a vynásobíme ho počtom, koľkokrát programopakujte slučku. Všetky slučky, ktoré rastú úmerne k veľkosti vstupu, majú lineárnu časovú zložitosť O(n). Ak prejdete len cez polovicu poľa, stále je to O(n).
