面试题：Python递归函数在复杂数据结构中的应用

Question

假设有一个嵌套的列表结构，例如[[1, 2, [3, 4]], 5, [6, [7, 8]]]，编写一个Python递归函数，将这个嵌套列表展开成一个单一的列表，并且分析该递归函数的时间复杂度和空间复杂度。

Answer 1

def flatten(lst):
    result = []
    for item in lst:
        if isinstance(item, list):
            result.extend(flatten(item))
        else:
            result.append(item)
    return result

时间复杂度分析

假设嵌套列表中总共有 (n) 个元素。在最坏情况下，每个元素都需要被访问一次，并且每次递归调用都会处理一部分元素。每次递归调用时，会遍历当前列表中的所有元素，所以时间复杂度为 (O(n))。

空间复杂度分析

空间复杂度主要来自于递归调用栈。在最坏情况下，递归的深度等于嵌套列表的最大深度 (d)。每次递归调用都会占用一定的栈空间，所以空间复杂度为 (O(d))。如果列表是高度嵌套的，那么 (d) 可能接近 (n)，此时空间复杂度接近 (O(n))；如果嵌套深度较浅，空间复杂度会远小于 (O(n))。