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

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

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