Теория сложности вычислений — подраздел теоретической информатики, занимающейся исследованием сложности алгоритмов для решения задач на основе формально определённых моделей вычислительных устройств. Сложность алгоритмов измеряется необходимыми ресурсами, в основном это продолжительность вычислений или необходимый объём памяти. В отдельных случаях исследуются другие степени сложности, такие как размер микросхем, или количество процессоров, необходимая для работы параллельных алгоритмов.
Следует не путать теорию сложности вычислений с теорией вычислимости, которая занимается поиском ответа на вопрос о том, какие задачи могут быть вообще решены с помощью алгоритмов. Основная задача исследований в теории сложности вычислений заключается в классификации всех разрешимых задач. В частности, делаются попытки разделить множество задач с эффективными алгоритмами решения от множества трудно разрешимых задач.
Вычислительную сложность алгоритма обычно выражают через символ «О прописная», что указывает порядок величины вычислительной сложности. Это просто член разложения функции сложности, которая растет быстрее при росте n, а все члены низшего порядка игнорируются. Например, если временная сложность порядка n2, то она выражается как O(n2) .
Не нужно знать ни точного времени выполнения отдельных инструкций, ни числа битов, которые представляют различные переменные, ни даже скорости процессора. Один компьютер может быть на 50 % быстрее другого, а у третьего ширина шины данных может быть вдвое больше, однако сложность алгоритма, оцененная по порядку величины, не изменится. При оценке довольно сложных алгоритмов всем остальным можно пренебречь (с точностью до постоянного множителя).
Оценка вычислительной сложности наглядно демонстрирует, как объём входных данных влияет на требования к времени и объёму памяти.
Например, если T=O(n), удвоение входных данных удвоит и время выполнения алгоритма. Если T=O(2n), то добавления лишь одного бита к входным данным удвоит время выполнения алгоритма.