#algorithm #time-complexity #permutation
Вопрос:
Автор утверждает, что временная сложность этого алгоритма перестановки:
from collections import deque
def find_permutations(nums):
nums_l = len(nums)
perms = deque()
perms.append([])
for num in nums: # (1)
for _ in range(len(perms)): # (2)
perm = perms.popleft()
for j in range(len(perm) 1): # (3)
new_perm = list(perm) # (4)
new_perm.insert(j, num) # (5)
perms.append(new_perm) # (6)
return perms
является n*n!
Но я не понимаю, почему. Вот мое вычисление временной сложности для каждой строки кода:
(1): len(nums) ~ n
(2): len(perms) ~ n!
(3): len(perm) ~ n
(4): n
(5): n
(6): n
Таким образом, общая временная сложность составляет:
n * n! * n * (n n n) ~ n^3 * n!
Или я ошибаюсь?
Ответ №1:
Прежде чем перейти к основной проблеме, на шаге (6) обнаружена незначительная ошибка: append это O(1). Но это не влияет на общую сложность.
Ваш анализ идет неправильно на шаге (2):
for _ in range(len(perms)):
Это не выполняет O(n!) итераций. В первый раз он даже выполняет только 1 итерацию, во второй раз все еще 1 итерацию, а в третий раз 2 итерации, затем 2 * 3, затем 2 * 3 * 4, … и в последний раз (n-1)! итерации.
Затем на шаге (3)также происходит переоценка:
for j in range(len(perm) 1)
Размер perm изначально невелик (соответствует циклу шага 2): сначала перестановки имеют размер 0, затем на следующей итерации внешнего цикла они имеют размер 1, … затем 2, … до n-1.
Таким образом, для общего числа итераций внутреннего цикла мы имеем эту сумму:
1 * 1 1 * 2 2 * 3 (2 * 3) * 4 … кей! … н!
Более простой способ взглянуть на это-понять, что на каждой итерации внешнего цикла этот код создает все перестановки, которые на один элемент длиннее, чем на предыдущей итерации. Таким образом, на первой итерации вы получаете все перестановки размера 1 (используя первое входное значение), на второй итерации вы получаете все перестановки размера 2 (используя два первых входных значения) и т. Д. Это подход «снизу вверх». Также обратите внимание, что popLeft выполняется нужное количество раз, чтобы удалить все перестановки предыдущей (внешней) итерации, в то время append как выполняется для всех новых перестановок (которые появляются только в следующей внешней итерации).
Таким образом, теперь мы можем легко видеть, что append выполняется это количество раз:
1! 2! 3! 4! … n! = O(n!)
Если мы теперь включим в это сложность шага 4 (который «поглощает» сложность шага 5), то получим:
1.1! 2.2! 3.3! 4.4! … n.n! = O(n.n!)
Комментарии:
1. Как насчет сложности шага 1? Это также должно быть O(n). Таким образом, похоже, что общая сложность будет O(n.n.n!), верно? Спасибо.
2. Нет, шаг 1 включен, когда я написал «для общего числа итераций внутреннего цикла» — я обновил фразу, чтобы указать, что учитывается внешний цикл.
3. Похоже, я наконец-то это понял. Если мы сравним алгоритм перестановки с чем-то с временной сложностью n^2, например [i для i в диапазоне(n) для j в диапазоне(n)], Разница в том, что для алгоритма перестановки у нас разное количество исключений на каждом шаге, поэтому временная сложность будет просто сложностью последнего шага (n!). Но для алгоритма n^2 у нас есть n исполнений для каждого внешнего цикла, например, для n =5: O(5 5 5 5 5) = O(5*5) или O(n^2). Чтобы сравнить его с алгоритмом перестановок, у нас есть временная сложность O(1! 2! 3! 4! …) и конечная сложность будет просто сложностью последнего шага (n!)
Ответ №2:
Этот алгоритм генерирует перестановки, вставляя число во все возможные позиции существующих перестановок
теперь первый цикл четко O(n)
давайте посмотрим, что происходит с другими циклами:
на последней итерации (в худшем случае):
- просмотр всех
(n-1)!перестановок (сгенерированных с помощью предыдущих итераций) —O((n-1)!) - копирование каждого из них и добавление нового номера внутри
O(n)каждого
в общей (n-1)! * (n) = n! сложности это для наихудшего случая других циклов
так что O(n * n!) в целом
Комментарии:
1. разве это не
O(n * n!)простоO(n!)в Большом О?