python - 如果项目数量未知,如何计算此展平数组函数的运行时复杂度?

标签 python arrays big-o flatten

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

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),其中 ndm 代表items 的大小、嵌套列表的最大深度以及最深列表中的最大元素数。

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

相关文章:

python - 我正在制作一款打砖 block 游戏,想知道是否有一种方法可以将这些砖 block 放在一个变量下

Python 文件 write() 没有正确写入/格式化

python - scikit-image 将图像保存到字节串

Python3 将所有字符转换为 HTML 实体

c++ - 指向数组转换的指针

javascript - react 显示子组件值的总和不准确

algorithm - 识别哪个算法是哪个并解释运行时间

python - 没有字符串连接的两个字符串的最长公共(public)序列 O(mn)

C将指针传递给函数,如何?

c - Big O 如何跟踪快速排序算法中的迭代? C