提问者:小点点

Python中zip()的时间复杂度是多少?


如何计算zip()的时间复杂度?

testList = [[1,2,3]for _ in range(5)]
zip(*testList)

共1个答案

匿名用户

假设您压缩了N个可迭代对象。

在python 3. x中,zip函数本身在O(1)时间运行,因为它只是分配一个特殊的可迭代对象(称为zip对象),并将参数数组分配给一个内部字段。函数调用本身(在控制到达zip之前)是O(N),因为解释器必须将参数转换为数组。迭代器上的每个后续next调用也在O(N)中运行。因此,耗尽zip对象是O(N*M)假设M是可迭代对象的平均(或最小)长度,不包括可迭代对象本身生成项目所需的时间(因为它独立于zip)。

在python 2. x中,zip函数返回一个列表。该列表必须在调用期间构建,这相当于耗尽前面示例中的迭代器,因此O(N*M),不包括压缩迭代表所花费的时间。