Хочется примеров задач, число операций в которых растет с экспотенциальным ростом ( n! или 2 в стенени n )

Здравствуйте, Аноним, Вы писали:

А>Хочется примеров задач, число операций в которых растет с экспотенциальным ростом ( n! или 2 в стенени n )
Это как? Потенция была-была и теперь нету?
Открываем Сиену или книгу Гэри-Джонсон.
Например, задача коммивояжера пока не решается в общем виде только экспоненциальным алгоритмом — полный перебор.

Здравствуйте, Аноним, Вы писали:

А>Хочется примеров задач, число операций в которых растет с экспотенциальным ростом ( n! или 2 в стенени n )

Насколько помню лекцию по дин. программированию, вычисление чисел Фибоначчи классическим рекурсивным способом имеет сложность примерно O(1,5 ^ n).
Псевдокод:

function fib(n: Integer): Integer;
begin
  if (n <= 2) then
    fib = 1
  else
    fib = fib(n-1) + fib(n-2);
end;

Здравствуйте, andy1618, Вы писали:

A>Здравствуйте, Аноним, Вы писали:

А>>Хочется примеров задач, число операций в которых растет с экспотенциальным ростом ( n! или 2 в стенени n )

A>Насколько помню лекцию по дин. программированию, вычисление чисел Фибоначчи классическим рекурсивным способом имеет сложность примерно O(1,5 ^ n).
A>Псевдокод:
A>

A>function fib(n: Integer): Integer;
A>begin
A>  if (n <= 2) then
A>    fib = 1
A>  else
A>    fib = fib(n-1) + fib(n-2);
A>end;
A>

Ну тут она тривиально упрощается в линейную. А вот коммивояжёра, укладку рюкзака и тому подобное — так не получится (если не считать локальных эмпирик)

Здравствуйте, Аноним, Вы писали:

А>Хочется примеров задач, число операций в которых растет с экспотенциальным ростом ( n! или 2 в стенени n )

Нужны примеры NP-трудных задач, NP-полных или именно экспоненциальных?
Факториал — это (n/e)^n, круче, чем экспонента.

Вычисление определителя матрицы "по определению" — это забег по всем перестановкам индексов, то есть факториал.
(Вычисление его же методом Гаусса — за кубическое время).

Любые функции, которые определены через операцию инкремента и дающие экспоненциальное значение.
Те же самые числа Фибоначчи:

F(0) = F(1) = 1
F(n) = F(n-1) + F(n-2)

разворачивается в F(n) = 1+1+1...., но мы-то знаем, что там ответ — экспонента с золотым сечением в основании



Кстати, отличная функция есть, которая гораздо круче факториала.

A(0,n) = n+1
A(m,0) = A(m-1,1)
A(m,n) = A(m-1, A(m,n-1))

Поскольку в натуральных числах она стремительно улетает, то можно попробовать посчитать её в конечной арифметике. Например, для uint64, чтобы не было соблазна тупо мемоизировать все значения.

Здравствуйте, Аноним, Вы писали:

А>Хочется примеров задач, число операций в которых растет с экспотенциальным ростом ( n! или 2 в стенени n )

Надо уточнить два момента:
1) нужен пример именно задачи, которая в общем случае не решается быстрее чем за экспоненциальное число операций или пример алгоритма, который выполняет экспоненциальное число шагов? Я так понимаю, что первое, тк второе — тривиально.
2) рассматриваются только детерминированные машины или вообще? Если вообще, то надо понимать, что классы EXPTIME и NP — разные (между ними еще PSPACE втиснулся), поэтому NP-полные задачи не удовлетворяют твоему условию (а то тут уже начали коммивояжера приводить, который проще чем EXPTIME).

Классическим примером EXPTIME-трудной задачи является, например, задача вычисления оптимальной стратегии в (обобщенных) шахматах. Доказательство можно найти, например, тут:

Aviezri S. Fraenkel and David Lichtenstein, Computing a perfect strategy for NxN chess requires time exponential in N, J. Combin. Theory Ser. A 31 (1981), no. 2, 199-214

Здравствуйте, Аноним, Вы писали:

А>Хочется примеров задач, число операций в которых растет с экспотенциальным ростом ( n! или 2 в стенени n )

Обезьянья сортировка, среднее время работы O(n*n!)