Существуют ли реальные O (n ^ n) алгоритмы?

Question

Есть ли какой-нибудь реальный алгоритм с временной сложностью O (n ^ n), который не просто уловка?

Я могу создать такой алгоритм, как вычисление n ^ n в O (n ^n) / Θ (n ^ n):

long n_to_the_power_of_m(int n, int m) {
    if(m == 0) return 1;
    long sum = 0;
    for(int i = 0; i < n; ++i)
        sum += n_to_the_power_of_m(n, m-1);
    return sum;
}

(требуется более 4 минут для вычисления 10 ^ 10)

Или наоборот: есть ли проблемы, которые не могут бытьрешается лучше, чем в O (n ^ n)?

Answer 1

То, что вы кодировали в своем примере, очень похоже на поиск в глубину. Итак, это один ответ.

Алгоритм поиска в глубину без каких-либо специальных характеристик (например, реконвергентных путей, которые можно оптимизировать) должен быть n ^ n.

Это на самом деле не надуманный пример. Шахматные программы работают по тому же алгоритму. Для каждого хода нужно рассмотреть n ходов (то есть ответвлений), и вы ищете d ходов вглубь. Так что становится O (n ^ d)

Answer 2

Существуют вычисления (например, tetration ), где размер вывода равен O (n ⁿ ). Их довольно сложно вычислить с временной сложностью меньше, чем O (n ⁿ ).

Answer 3

Согласно Википедии , существуют некоторые двойные экспоненциальные проблемы времени O (2 ^{2 poly (n)} ), которые более сложны, чем O (n ⁿ ), например, "Процедуры принятия решения для Пресбургерской арифметики " (O (2 ^{2 cn} )) и "Вычисление Грёбнерабазис"(в худшем случае O (2 ^{2 n / 10} )

Answer 4

Есть много проблем оптимизации, которые по существу O (n!), То есть в сжатии данных.Обычные алгоритмы для всего этого должны так или иначе обманывать (многие полагаются на эвристику), но не могут быть уверены, что таким образом они достигли идеального результата.Т.е. выбор оптимальных линейных фильтров во время сжатия PNG-изображения - это такая проблема, которая сравнительно проста для понимания.

Другим примером являются алгоритмы, нарушающие шифрование, которые потенциально могут быть даже хуже, чем O(п!).

Answer 5

Программа, которая принимает описание (завершающей) машины Тьюринга и возвращает количество шагов, необходимых для ее завершения. Это относительно простая программа для написания - она ​​может просто эмулировать машину Тьюринга и подсчитывать шаги.

Сложность этой программы не имеет вычисляемой верхней границы (и, в частности, растет быстрее, чем любая вычислимая функция), поэтому, безусловно, растет быстрее, чем O (n ^ n).

Наихудшее время выполнения на входе размера n - BB (n), последовательность Busy Beaver , которая начинается 0, 1, 4, 6, 13, после этого неизвестна ( хотя существуют нижние границы - например, следующие два значения по крайней мере 47176870 и 7,412 × 10 ^ 36534 соответственно) и не вычислимы для достаточно большого n.