python - Python 中 zip() 的时间复杂度是多少？

Question

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

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

Answer 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)，不包括在压缩迭代中花费的时间。