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

Существует ли какой-либо реальный алгоритм с временной сложностью 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;
}

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

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

Ответ 1

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

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

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

Ответ 2

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

Ответ 3

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

Ответ 4

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

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

Ответ 5

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

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

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