В інформатиці, теорія складності обчислень є розділом теорії обчислень, що вивчають вартість роботи, необхідної для вирішення обчислювальної проблеми. Вартість вимірюється абстрактними поняттями часу і простору, званими обчислювальними ресурсами. Час визначається кількістю елементарних кроків, необхідних для знаходження рішення, а простір - об'ємом пам'яті, які застосовуються у цьому процесі.
Таким чином, робиться спроба відповісти на центральне питання розробки алгоритмів: «як зміниться час виконання і обсяг використаної пам'яті в залежності від розміру вхідних даних і результату?».
Поняття алгоритму формувалося з найдавніших часів [1], [2]. але до кінця першої третини XX ст. математики задовольнялися інтуїтивним уявленням про цей об'єкт. Термін «алгоритм» вживався в математиці лише в зв'язку з тими чи іншими конкретними алгоритмами. Твердження про існування алгоритму для вирішення завдань деякого типу супроводжувалося фактичним його описом.
Кожен алгоритм передбачає наявність деяких початкових, або вихідних, даних, а в результаті застосування призводить до отримання певного бажаного результату.
Застосування кожного алгоритму здійснюється шляхом виконання дискретної ланцюжка (послідовності) деяких елементарних дій. Ці дії називають кроками, а процес їх виконання називають алгоритмічним процесом. Таким чином, наголошується властивість дискретності алгоритму. Суттєвою рисою алгоритму є його масовий характер, тобто можливість застосовувати його до обширного класу початкових даних. Іншими словами, кожен алгоритм покликаний вирішувати клас однотипних завдань.
Неодмінною умовою, якому задовольняє алгоритм, є його детермінованість, або визначеність. Це означає, що приписи алгоритму настільки точні і виразні, що не допускають ніяких двозначних тлумачень. Вони єдиним і цілком визначеним шляхом призводять до шуканого результату.
Що таке складність завдання? Алгоритмічна складність самого простого її рішення.
З практичної точки зору, уявлення про складність алгоритму допомагає:
кількісно і якісно порівнювати різні рішення однієї і тієї ж проблеми
оцінити складність вирішуваної проблеми