我有两个函数，这两个函数都可以在Python中展平任意嵌套的列表列表。
我试图弄清楚两者的时间复杂度，看看哪个更有效，但到目前为止，我还没有找到任何关于 SO 的明确内容。关于列表列表有很多问题，但还没有达到嵌套的第n个程度。
函数 1(迭代)
def flattenIterative(arr):
i = 0
while i < len(arr):
while isinstance(arr[i], list):
if not arr[i]:
arr.pop(i)
i -= 1
break
else:
arr[i: i + 1] = arr[i]
i += 1
return arr
函数 2(递归)
def flattenRecursive(arr):
if not arr:
return arr
if isinstance(arr[0], list):
return flattenRecursive(arr[0]) + flattenRecursive(arr[1:])
return arr[:1] + flattenRecursiveweb(arr[1:])
我的想法如下：
函数 1 复杂性
我认为迭代版本的时间复杂度是O(n * m)，其中n是初始数组的长度，m是嵌套量。我认为O(n)的空间复杂性n是初始数组的长度。
函数 2 复杂度
我认为递归版本的时间复杂度将O(n)其中n是输入数组的长度。我认为O(n * m)的空间复杂度n是初始数组的长度，m是嵌套的深度。
总结
所以，对我来说，迭代函数似乎更慢，但空间更有效。相反，递归函数更快，但空间效率较低。这是对的吗？
我不这么认为。有 N 个元素，因此您需要至少访问每个元素一次。总体而言，您的算法将运行 O(N) 迭代。决定因素是每次迭代发生的情况。
您的第一个算法有 2 个循环，但如果您仔细观察，它仍然每次迭代每个元素 O(1) 次。然而，正如@abarnert所指出的，arr[i: i + 1] = arr[i]将每个元素从arr[i+1:]向上移动，这又是O(N)。
您的第二种算法类似，但在本例中您正在添加列表(在前一种情况下，它是简单的切片分配)，不幸的是，列表添加的复杂性是线性的。
总之，你的两种算法都是二次的。