Skaitmeninio sudėtingumo teorija yra teorinės kompiuterinės mokslo ir matematikos skaičiavimo teorijos dalis, kurioje pagrindinis dėmesys skiriamas skaičiavimo problemų klasifikavimui pagal jų sudėtingumą. Ypač dažni programavimo metu yra * laiko ir erdvės amortizuota analizė *

Atsižvelgiant į problemą ir skaičiavimo modelį, modelio sudėtingumo problema priklauso nuo įvesties dydžio, o sudėtingumo funkcijos gali matuoti įvairius kiekius, tokius kaip laikas arba erdvė:

  • Laikinasis sudėtingumas lemia, kiek laiko modelis ima išspręsti problemą, pagrįstą įvestimi.
  • Erdvės sudėtingumas matuoja, kiek atminties reikia modeliui, kad išspręstų įvesties problemą.

Kaip priemonę, sudėtingumą galima apibrėžti kaip funkciją:

 c = f(n) 

kur n yra įvesties dydis.

Paprastai sudėtingumas klasifikuojamas pagal analitinę formą f (n). Pavyzdžiui, jei f(n) = n , sudėtingumas yra tiesinis n . Jei f(n) = n 2 tada sudėtingumas yra kvadratinis. Jei f(n) = 2 n tada sudėtingumas yra eksponentinis.