Algoritminis sudėtingumas (skaičiavimo sudėtingumas arba Kolmogorovo sudėtingumas) yra pagrindinė tiek skaičiavimo sudėtingumo teorijos, tiek algoritminės informacijos teorijos idėja ir atlieka svarbų vaidmenį formalioje indukcijoje.
Dvejetainės eilutės algoritminis sudėtingumas apibrėžiamas kaip trumpiausia ir efektyviausia programa, galinti sukurti eilutę. Nors yra begalė programų, kurios gali sukurti bet kurią eilutę, viena programa ar programų grupė visada bus trumpiausia. Nėra algoritminio būdo rasti trumpiausią algoritmą, kuris išveda nurodytą eilutę; tai vienas pirmųjų skaičiavimo sudėtingumo teorijos rezultatų. Nepaisant to, galime pagrįstai spėti. Šis rezultatas (eilutės skaičiavimo sudėtingumas) pasirodo esąs labai svarbus įrodymams, susijusiems su apskaičiuojamumu.
Kadangi bet kurį fizinį objektą ar savybę iš esmės galima apibūdinti iki beveik išnaudotos bitų eilutės, galima sakyti, kad objektai ir savybės taip pat turi algoritminį sudėtingumą. Tiesą sakant, realaus pasaulio objektų sudėtingumo sumažinimas iki programų, kurios gamina objektus kaip išvestį, yra vienas iš būdų pažvelgti į mokslo įmonę. Mus supantys sudėtingi objektai paprastai atsiranda dėl trijų pagrindinių generavimo procesų; atsiradimas, evoliucija ir intelektas, kurių kiekvieno sukurti objektai linkę į didesnį algoritminį sudėtingumą.
Skaičiavimo sudėtingumas yra sąvoka, dažnai naudojama teorinėje informatikos moksle, siekiant nustatyti santykinį sudėtingumą skaičiuojant įvairių matematinių ir loginių problemų sprendimus. Egzistuoja daugiau nei 400 sudėtingumo klasių, o papildomos klasės nuolat atrandamos. Garsusis P = NP klausimas susijęs su dviejų iš šių sudėtingumo klasių prigimtimi. Sudėtingumo klasės apima daug sunkesnių užduočių, su kuriomis galima susidurti matematikoje iki skaičiavimo. Skaičiavimo sudėtingumo teorijoje yra daug įsivaizduojamų problemų, kurioms išspręsti prireiktų beveik be galo daug laiko.
Algoritminį sudėtingumą ir susijusias koncepcijas septintajame dešimtmetyje sukūrė dešimtys tyrinėtojų. Andrejus Kolmogorovas, Ray Solomonoff ir Gregory Chaitinas septintojo dešimtmečio pabaigoje labai prisidėjo prie algoritminės informacijos teorijos. Mažiausio pranešimo ilgio principas, glaudžiai susijęs su algoritmo sudėtingumu, sudaro didžiąją dalį statistinių ir indukcinių išvadų bei mašininio mokymosi pagrindų.