Здравствуйте!
Имеется такая задача:
"Перестановки". Напишите алгоритм нахождения всех перестановок целых чисел от 1 до N. Указание: Множество перестановок целых чисел от 1 до N можно получить из множества перестановок целых чисел от 1 до N − 1, вставляя N во все возможные позиции в каждой перестановке длины N − 1.
Как реализовать данную задачу рекурсивно, я представляю и смогу сделать, в этом нет проблемы.
Суть в том, что я не совсем пойму с временной сложностью этой программы.
Можно так задать вопрос:
Является ли задача NP-полной, или P-задачей, или иной. И почему?
И при каких значениях N данная задача реально решаемая за разумное время на домашнем ПК?
Собственно, проблема у меня с оценкой этой задачи.
Разъясните, пожалуйста, кто знает.
Спасибо!