Big O Обозначение для перестановок списка слов

Question

Что было бы большим обозначением O длины списка перестановок символов списка слов длины n?

Я просто не знаю, как выразить это, потому что это будет как п! для каждого слова, где n - это символы этого слова, но O (n!) - это просто сложность одного слова, а не список n слов.

Кроме того, каждое слово может иметь разные размеры.

Пример:

Давайте предположим, что у меня есть слова "ABC", "ABCD" и "ABCDE". Если мне нужно создать перестановки для каждого слова, я бы привел список списков строк длиной 6, 24 и 120, т. Е. Перестановки «abc» будут в первом списке, перестановки второго слова будет во втором и т. д. и так далее.

Если я использую итератор перестановки, сколько времени потребуется для создания всех этих списков?

Answer 1

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

Если у вас есть дополнительная информация о распределении этих длин мы можем попытаться сделать более жесткий предел :-)

@Edit: а @Aron отметил, что это довольно (я не догонят очень формальная здесь) плотная верхняя граница, если у вас нет повторений символов. С повторяющимися символами это по-прежнему действительная верхняя граница, но более жесткая привязка будет O(k*a^n), где a - это размер нашего алфавита (26, если вы используете английский язык, более 110 000, если вы используете Unicode), это в конечном итоге будет более плотным, чем O(k*n!). Это связано с тем, что в каждом из слотов n вы можете разместить один из символов a и заметить, что с повторяющимися символами a может быть меньше (даже намного меньше), чем n.