asymptotický odhad zložitosti

Text hesla

asymptotický odhad zložitosti — metóda približného odhadu výpočtovej zložitosti algoritmov alebo úloh, ktorý sa tým viac približuje ku skutočnej hodnote, čím viac sa nejaký parameter priblíži k limitnej hodnote.

Predpokladajme, že funkcie \(f\) a \(g\) sú nezáporné. Horným ohraničením funkcie \(f\) je funkcia \(g\) práve vtedy, ak existujú také dve kladné konštanty \(c\) a \(n_0\), že \(f(n) \le c\cdot g(n)\) pre všetky \(n\), \(n \ge n_0,\) čo sa zapisuje ako

\(f(n) = O(g(n)).\)

Dolným ohraničením funkcie \(f\) je funkcia \(g\) práve vtedy, ak existujú také dve kladné konštanty \(c\) a \(n_0\), že \(f(n) \ge c\cdot g(n)\) pre všetky \(n\), \(n\ge n_0\), čo sa zapisuje ako

\(f(n) = \mathrm{\Omega}(g(n)).\)

Okrem zápisov \(O\) a \(\mathrm{\Omega }\) sa zavádza aj zápis \(\Theta\) ako ich kombinácia. Ohraničením funkcie \(f\) je funkcia \(g\) práve vtedy, ak existujú také tri kladné konštanty \(c_1\), \(c_2\) a \(n_0\), že \(c_1\cdot g(n) \le f(n) \le c_2\cdot g(n)\) pre všetky \(n\), \(n\ge n_0\), čo sa zapisuje ako

\(f(n) = \Theta(g(n)).\)

Uvedené zápisy sa používajú na vyjadrenie asymptotického odhadu zložitosti algoritmov. Metóda ich určenia je jednoduchšia, než by bolo presné zisťovanie zložitosti. Ak je napr. asymptotický odhad zložitosti nejakého algoritmu \(O(n)\), znamená to, že pre dostatočne veľké \(n\) presná hodnota zložitosti (napr. času výpočtu alebo množstva pamäte) nie je väčšia než \(c\cdot n\) pre nejaké \(c\). Ak je asymptotický odhad zložitosti nejakého algoritmu \(\mathrm{\Omega }(n^2)\), znamená to, že pre dostatočne veľké \(n\) presná hodnota zložitosti (napr. času výpočtu alebo množstva pamäte) nie je menšia než \(c\cdot n^2\) pre nejaké \(c\). Pomocou asymptotického odhadu zložitosti možno algoritmy aj porovnávať z hľadiska zložitosti. Napr. algoritmus so zložitosťou \(O(n)\) je lepší než algoritmus so zložitosťou \(O(n\cdot \log n)\), ten je lepší než \(O(n^2)\) atď.

Zverejnené v auguste 1999.

Asymptotický odhad zložitosti [online]. Encyclopaedia Beliana, ISBN 978-80-89524-30-3. [cit. 2023-12-02]. Dostupné na internete: https://beliana.sav.sk/heslo/asymptoticky-odhad-zlozitosti