Описание тега complexity-theory
Теория сложности вычислений - это раздел теории вычислений в теоретической информатике и математике, который фокусируется на классификации вычислительных задач в соответствии с присущей им сложностью. В программировании особенно часто используется * амортизированный анализ * для времени или пространства.
Учитывая проблему и вычислительную модель, сложность проблемы по отношению к модели является функцией размера входных данных. Функции сложности могут измерять разные величины, такие как время или пространство:
- Сложность времени измеряет, сколько времени требуется модели для решения проблемы с учетом входных данных.
- Сложность пространства определяет, сколько места в памяти требуется модели для решения проблемы с учетом входных данных.
В качестве меры сложность можно определить как функцию:
c = f(n)
где n - размер ввода.
Обычно сложность классифицируется с помощью аналитической формы f(n). Например, еслиf(n) = n, сложность линейна относительно n. Еслиf(n) = n2, то сложность квадратичная. Еслиf(n) = 2n, то сложность экспоненциальна.