Пространственная и временная сложность выравнивания вложенного списка произвольной глубины ⇐ Python

[Anonymous]

При наличии списка Python, который содержит вложенные списки произвольных уровней вложенности, цель состоит в том, чтобы вернуть полностью плоский список, т.е. для образца входных данных [1, [2], [[[3]]], 1], вывод должен быть [1, 2, 3, 1].
Мое решение:

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

def flatten(lst):
stack = [[lst, 0]]
result = []

while stack:
current_lst, start_index = stack[-1]
for i in range(start_index, len(current_lst)):
if isinstance(current_lst[i], list):
# Update the start_index of current list
# to the next element after the nested list
stack[-1][1] = i + 1
# Add nested list to stack
# and initialize its start_index to 0
stack.append([current_lst[i], 0])
# Pause current_lst traversal
break
# non list item
# add item to result
result.append(current_lst[i])
else:
# no nested list
# remove current list from stack
stack.pop()

return result

Я хотел бы знать временную и пространственную сложность (вспомогательное пространство) моего решения, если оно правильное.
Что я думаю
Временная сложность:
Я считаю, что временная сложность решения равна O (m + n) где m — общее количество вложенные списки на всех уровнях, а n — общее количество атомарных элементов на всех уровнях (элементы, не относящиеся к списку)
Пространственная сложность:
Я считаю, что пространственная сложность равна O(d), где d — глубина самого вложенного списка. Это связано с тем, что стек отслеживает текущее состояние обхода, а его размер пропорционален глубине вложенности.
Правильно ли решение?
Правильно ли анализ времени и пространства верен?

Подробнее здесь: https://stackoverflow.com/questions/792 ... rary-depth