Python中zip()的时间复杂度是多少?
答
假设您压缩N次迭代。
在蟒3.X,zip函数本身在O(1)
时间用完,因为它只是分配特别可迭代(称为拉链对象),和参数数组到内部字段分配。函数调用本身(在控件到达zip之前)为O(N)
,因为解释器必须将参数转换为数组。在迭代器上调用的每个后续next
也都在O(N)
中运行。因此,假设M是迭代次数的平均(或最小)长度,排除迭代本身用于生成项目(因为它独立于zip)的时间,因此耗尽zip对象为O(N*M)
。
在python 2.x,zip函数返回一个列表。该列表必须在调用期间构建,这相当于耗尽前面示例中的迭代器,因此O(N*M)
不包括在压缩的可迭代中花费的时间。
它的O(N * M)其中N是最短列表的长度,M是列表数量 –
您需要区分是否使用python 2或python 3作为'zip'在两个函数中都有不同的功能。 –
调用本身,我猜是O(1)在python 3 ...但评估仍然是相同的,我认为...也许我完全错了 –