Пояснение к алгоритмической задаче. Перестановки целых чисел

Рейтинг: 1Ответов: 1Опубликовано: 09.12.2014

Здравствуйте!

Имеется такая задача:

"Перестановки". Напишите алгоритм нахождения всех перестановок целых чисел от 1 до N. Указание: Множество перестановок целых чисел от 1 до N можно получить из множества перестановок целых чисел от 1 до N − 1, вставляя N во все возможные позиции в каждой перестановке длины N − 1.

Как реализовать данную задачу рекурсивно, я представляю и смогу сделать, в этом нет проблемы.

Суть в том, что я не совсем пойму с временной сложностью этой программы.

Можно так задать вопрос:

Является ли задача NP-полной, или P-задачей, или иной. И почему?

И при каких значениях N данная задача реально решаемая за разумное время на домашнем ПК?

Собственно, проблема у меня с оценкой этой задачи.
Разъясните, пожалуйста, кто знает.

Спасибо!

алгоритм комбинаторика
Источник: Stack Overflow на русском

Ответы

▲ 4Принят

Согласно определению, классификация проблем P/NP относится к задачам, имеющим ответом «да» или «нет». Поскольку ваша задача таковой не является, она не относится ни к одному из этих классов.

Ваш К. О.

Обновление

С временной сложностью, поскольку нужно вывести n! перестановок, то в лучшем случае O(n!) = O(sqrt(n) (n/e)^n) = O(sqrt(n) exp(n ln n - n)). То есть даже больше, чем экспонента. Так что всё довольно кисло.

Насколько мне помнится, вычисление каждой следующей перестановки можно свести к O(1) или в крайнем случае O(log n), так что реальный ответ будет не сильно отличаться от оценки.

Обновление 2

@avp: Будем отталкиваться от 1 Г/с. Для записи перестановки размером n нужно по идее n log_2 n бит. Поскольку всех перестановок около sqrt(n * 2 * pi) (n/e)^n, суммарное количество байт около sqrt(2 * pi)/8 * n^1.5 * log_2 n * (n/e)^n, время sqrt(2 * pi)/8 * n^1.5 * log_2 n * (n/e)^n / 2^30 сек.

Вот что получается: http://pastebin.com/sgRVsBAm

При n >= 10 уже нереалистично.

Обновление 3

И правда, ошибся, кодируя формулу Стирлинга. Надо делить на e, а я умножил.

Скорректированный результат: http://pastebin.com/AdVCmHBJ