我有一个函数压平给定的数组。
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)
我不知道如何计算这个函数的运行时复杂度?
最佳答案
因为我假设您关心最坏情况的性能,所以您可以考虑一个抽象的最坏情况示例,然后从中得出答案。
数据 = [[[[... [1, 2, 3, ..., m] ...]]], [[[... [1, 2, 3, .. ., 米] ...]]], ..., [[[... [1, 2, 3, ..., 米] ...]]]]
现在您可以轻松了解三个因素如何影响最坏的情况。 items
的大小、列表列表的深度,最后是最深列表中的元素数量。
因此,最坏情况的复杂度为 O(n x d x m)
,其中 n
、d
和 m
代表items
的大小、嵌套列表的最大深度以及最深列表中的最大元素数。
关于python - 如果项目数量未知,如何计算此展平数组函数的运行时复杂度?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/48475970/