komplexitás

Rövid szöveges bemutatás: 
A komplexitást egy problémára vagy algoritmusra lehet meghatározni. A komplexitással tudjuk kifejezni, hogy mennyire bonyolult egy adott feladat végrehajtása. A bonyolult kifejezést olyan értelemben kell venni, hogy arányában a bemenetek mennyiségétől függően mennyi ideig tart a feladat megoldása. Lehet például lineáris, amikor az algoritmus körülbelül annyi végrehajtási egységet igényel, amennyi a bemenet száma. De ezenkívül lehet szinte bármilyen függvénye a bemenetnek, exponenciális, faktoriális, stb... A polinomiális végrehajtási időtől komplexebb (legalább exponenciális) algoritmusokat általában nem hatékonynak nevezzük, illetve a maximum polinom időben végrehajtható algoritmusokat viszont hatékonynak nevezzük.