1

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

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

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

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

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

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

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

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

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

Спасибо!

1 ответ 1

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

10
  • А причем тут это? Есть класс P-задач, есть класс NP-задач. Решение о равенстве этих классов даст лишь возможность или невозможность решать NP-задачи за полиномиальное время, а не изменить список этих задач. 9 дек 2014 в 9:49
  • О как, действительно очевидно, как-то не задумывался об этом. Спасибо! А можете пояснить: что с временной сложностью данной задачи? Или тут нужно смотреть после реализации. 9 дек 2014 в 12:49
  • 2
    @Daniil Manin: Обновил ответ
    – VladD
    9 дек 2014 в 12:56
  • 2
    Причем на практике это время похоже будет определяться скоростью вывода результатов на носитель.
    – avp
    9 дек 2014 в 13:03
  • Спасибо! Вы мне очень помогли! 9 дек 2014 в 13:05

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.