Сложность кода Объяснение | Генерация PowerSet ⇐ Python

[Anonymous]

Я пытаюсь понять различия/сходства в сложностях при написании кода для генерации набора мощности двумя способами:

Код: Выделить всё

def powerset(s, i, cur):
if i==len(s):
print(cur)
return

powerset(s, i+1, cur+s[i]) # string addition is also possibly O(n^2) here?
powerset(s, i+1, cur)

powerset("abc", 0, "")

Выход:

Код: Выделить всё

['abc', 'ab', 'ac', 'a', 'bc', 'b', 'c', '']

Это происходит в рекурсии, с двумя вариантами выбора на каждом этапе (добавление s или нет), созданием 2 ветвей. Ведущий к 2^n и добавление к массиву/печати - это еще один O(n), ведущий к O(n*2^n)
Также думая об этом с точки зрения ветвей^глубина = O(2^n)
Пространственная сложность для этого будет: O(n)? Учитывая, что максимальная глубина дерева должна достигать n по приведенной выше логике.
И при этом:

Код: Выделить всё

s = "abc"
res = [""]

for i in s:
res += [j+i for j in res]

Я получаю тот же результат.
Но здесь я вижу 2 цикла for и дополнительную сложность создания строк, которая, возможно, равна O(n^2) в Python. Это приводит к возможному O(N^4) в отличие от O(n*2^n) в приведенном выше решении.
Пространственная сложность здесь кажется мне O(n), поскольку мы резервируем место только для вывода. Но дополнительного места нет, так что в целом: O(1)
Правильно ли я понимаю эти решения во времени и пространстве? У меня сложилось впечатление, что набор вычислительных мощностей равен O(2^n). Но я подумал, может быть, это более оптимизированное решение? (хотя второе решение кажется более наивным).

https://stackoverflow.com/questions/340 ... -on2-or-on

Здесь они предлагают использовать массивы, чтобы избежать сложности строки `O(n^2)` конкатенация.