嵌套列表扁平化算法的正确性验证及时间、空间复杂度分析问询

大家好，我现在在处理一个嵌套列表扁平化的问题：给定一个包含任意层级嵌套列表的Python列表，需要返回一个完全扁平化的列表。举个例子，如果输入是 [1, [2], [[[3]]], 1]，输出应该是 [1, 2, 3, 1]。

我自己写了一份Python解法，代码如下：

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 是嵌套列表的最大深度。原因是栈会跟踪每一层遍历的当前状态，栈的大小和嵌套深度成正比。

最后想请教两个问题：

• 我写的这份扁平化解法是否正确？
• 上面的时间、空间复杂度分析是否准确？

备注：内容来源于stack exchange，提问作者ariko stephen