В чем сложность генерации всех возможных последовательностей с применением оператора if в некоторых позициях

Question

У меня два вопроса.

Первый

Представьте, что у нас есть список из 3 элементов, n = [1,2,3], и мы хотим сгенерировать все возможные последовательности, гдедлина сгенерированного списка равна 7. В качестве примера, одна из возможных последовательностей имеет вид m = [1,2,3,1,1,2,3]

Первый вопрос: в чем сложность? экспоненциальный или полиномиальный?

Второй

Теперь у нас есть 7 элементов, как в предыдущем примере [1,2,3,1,1,2,3], и, если мы скажем, например, вв первой позиции (слева) мы хотели бы иметь только номер 1, во второй позиции 1 и 2, в третьей, четвертой и пятой позициях мы можем иметь все цифры (1,2,3), в шестойпозиции 1 и 2, а в последней позиции только 1, форма имеет форму колокола.

Какая сложность сейчас?

Answer 1

По | х |Я имею в виду длину x, под [x] наибольшее целое число, не превышающее x.

Первое:

Поскольку число различных возможностей равно | n | ^ | m |,временная сложность будет не менее O (| n | ^ | m |). Если вы возьмете | n |для постоянной и | m |как переменная, тогда временная сложность будет экспоненциальной (с | n | в качестве основы). С другой стороны, если вы возьмете | m |как исправить и только изменить | n |, то он становится полиномом. Пространственная сложность в обоих случаях линейна O (| n | + | m |).

Секунда:

Если | m |> 2 | n |тогда O ((| m | -2 | n |) ^ | n | * (| n |!) ^ 2), потому что две «стороны» имеют обе | n |! возможности, и «средняя часть» может быть заполнена чем-либо из n.

If | m |<= 2 | n |тогда O ([| m | / 2]!) если | m |четно и O ([| m | / 2]! * (m + 1) / 2), если | m |нечетное числоЭто почти то же самое, что и выше, но без «средней части». </p>

Сложность пространства по-прежнему равна O (| m | + | n |).