экспоненциальное время

EN: exponential time

Класс временной сложности, при котором время работы растёт как c^n при некоторой константе c > 1, чаще всего O(2ⁿ). Уже при n = 60 число 2⁶⁰ превышает 10¹⁸ шагов, делая алгоритм непрактичным. Такой рост демонстрируют перебор всех подмножеств, наивный рекурсивный Фибоначчи и некоторые точные решатели NP-трудных задач.