Výpočtová zložitosť alebo výpočtová náročnosť je pojem z teórie algoritmov, vyjadruje nakoľko je výpočet podľa zvoleného algoritmu zložitý. Výpočtovú zložitosť študuje teória zložitosti.

Výpočtová zložitosť má dve základné miery:

• časová zložitosť
• pamäťová zložitosť

Optimalizácia algoritmu sa týka minimalizácie jednej alebo obidvoch mier zložitosti.

Výpočtová zložitosť algoritmu priamo nesúvisí so zložitosťou samotného algoritmu z ľudského pohľadu. Algoritmus môže byť veľmi jednoduchý na pochopenie i implementáciu, napriek tomu môže byť jeho výpočtová zložitosť veľká a naopak.

Druhy výpočtovej zložitosti v závislosti od počtu vstupných prvkov n, (a,b,c sú konštanty, t je čas):

1. lineárna zložitosť: ${\displaystyle t=a.n+b}$
2. logaritmicko lineárna: ${\displaystyle t=a.n.log(n)+b.n+c}$
3. polynomiálna: t je funkciou nejakého polynómu n
4. algoritmy so zložitosťou väčšou než je polynomiálna

Za rýchle algoritmy sa pokladajú prvé tri druhy.

Ilustráciou zložitosti je nasledujúca tabuľka, predpokladajme, že vykonanie jednej operácie trvá jednu mikrosekundu:

Z uvedenej tabuľky vidno, že aj keby sme rýchlosť operácii zväčšili 1000x, posledný algoritmus by bol tak či tak neriešiteľný v rozumnom čase a predposledný pre väčšie n tiež.

Tú istú úlohu možno väčšinou riešiť rôznymi algoritmami s rozličnou výpočtovou zložitosťou. Napríklad triedenie sa dá jednoducho implementovať s výpočtovou zložitosťou n², ale existujú aj algoritmy triedenia so zložitosťou n.log n.

Tento článok týkajúci sa počítačov je zatiaľ „výhonok“. Pomôž Wikipédii tým, že ho doplníš a rozšíriš.