列表扁平化的时间复杂性

Question

我有两个函数，都是在Python中展开任意嵌套的列表列表。在

我试图弄清楚两者的时间复杂性，看看哪一个更有效，但到目前为止，我还没有找到任何明确的东西。关于列表列表有很多问题，但还没有到嵌套的第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（递归）

^{pr2}$

我的想法如下：

功能1复杂性

我认为迭代版本的时间复杂度是O(n * m)，其中n是初始数组的长度，m是嵌套量。我认为O(n)的空间复杂度，其中n是初始数组的长度。在

功能2复杂性

我认为递归版本的时间复杂性是O(n)，其中n是输入数组的长度。我认为O(n * m)的空间复杂性，其中n是初始数组的长度，m是嵌套的深度。在

总结

所以，在我看来，迭代函数速度较慢，但在空间上更有效。相反，递归函数更快，但在空间上效率较低。这是对的吗？在

Answer 1

我不这么认为。有N个元素，因此您需要至少访问每个元素一次。总的来说，您的算法将运行O（N）次迭代。决定因素是每次迭代发生的情况。在

您的第一个算法有2个循环，但是如果您仔细观察，它仍然在每个元素上迭代O（1）次。然而，正如@abarner所指出的，arr[i: i + 1] = arr[i]将每个元素从arr[i+1:]向上移动，这又是O（N）。在

第二个算法与之类似，但在本例中添加列表（在前一个示例中，这是一个简单的切片分配），不幸的是，列表添加的复杂性是线性的。在

总之，两种算法都是二次的。在