询问Python collections.deque非空构造函数的平均及摊还最坏时间复杂度

核心结论 #

当使用非空可迭代对象构造deque时，deque(iterable)的平均情况与摊还最坏情况时间复杂度均为O(n)，其中n是可迭代对象中的元素总数。原因是构造过程需要遍历所有元素并逐个添加到双端队列，而deque的元素添加操作摊还时间复杂度为O(1)每元素，整体复杂度随元素数量线性增长。

示例1分析 #

from collections import deque

answer = deque([[1, 4], [3, 9], [0, 2, 1], [3]])  

传入deque的列表包含4个元素（每个子列表作为独立元素），因此构造该deque的：

• 平均情况时间复杂度：O(4)（即O(1)，常数时间）
• 摊还最坏情况时间复杂度：O(4)（即O(1)，常数时间）

若用通用变量表述，设输入列表的元素数量为n，则复杂度为O(n)。

示例2分析 #

from collections import deque

def myfunc(mylist):
    res = []
    for i in mylist:
        res.append(deque(mylist))
    return res

answer = myfunc([[1, 4], [3, 9], [0, 2, 1], [3]])

函数myfunc会循环mylist的长度次（此处为4次），每次循环都构造一个包含mylist全部4个元素的deque（单次构造复杂度为O(4)）。因此总时间复杂度：

• 平均情况时间复杂度：4 × O(4) = O(16)（即O(1)，常数时间）
• 摊还最坏情况时间复杂度：4 × O(4) = O(16)（即O(1)，常数时间）

若用通用变量表述，设mylist的元素数量为n，则总复杂度为O(n²)，因为n次循环每次执行O(n)的操作。

内容的提问来源于stack exchange，提问作者croatoan