python - 如果项数未知，如何计算此扁平数组函数的运行时复杂度？

我有一个函数展平给定的数组。

def flatten(items):
    results = []
    for i in items:
        if isinstance(i, list):
            results += flatten(i)
        else:
            results.append(i)
    return results

效果很好。如下图所示，无法知道它将运行多少次。有很多嵌套数组。

data = [1, 2, 3, [4], [5, 6], [[7, 8, 9], 10, 11, 12], [13, 14, 15, [[[16], 17], 18, 19], [[[20, 21]]]], [[[22], 23, [[24]]]]]
data_flatten = flatten(data)

print(data_flatten)

我不知道如何计算此函数的运行时复杂度？

最佳答案

由于我假设您关心最坏的情况，因此可以考虑一个抽象的最坏情况的例子，然后从中得出答案。

data = [[[[... [1, 2, 3, ..., m] ...]]], [[[... [1, 2, 3, ..., m] ...]]], ..., [[[... [1, 2, 3, ..., m] ...]]]]

现在，您可以轻松了解最坏情况如何受到三个因素的影响。 items的大小，列表列表的深度，最后是最深列表中的元素数。

因此，最坏情况的复杂度是O(n x d x m)，其中n，d和m代表items的大小，嵌套列表的最大深度以及最深列表中元素的最大数量。

关于python - 如果项数未知，如何计算此扁平数组函数的运行时复杂度？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/48475970/