问题描述
限时送ChatGPT账号..如何计算 zip() 的时间复杂度?
How can I calculate the time complexity of zip()?
testList = [[1,2,3]for _ in range(5)]
zip(*testList)
推荐答案
假设你压缩了 N 个迭代.
Assume you zip N iterables.
在 python 3.x 中,zip 函数本身在 O(1)
时间内运行,因为它只分配一个特殊的可迭代对象(称为 zip 对象),并且将参数数组分配给内部字段.函数调用本身(在控制到达 zip 之前)是 O(N)
,因为解释器必须将参数转换为数组.迭代器上的每个后续 next
调用也在 O(N)
中运行.因此,耗尽 zip 对象是 O(N*M)
假设 M 是可迭代对象的平均(或最小)长度,不包括可迭代对象本身生成项目所需的时间(因为它独立于 zip).
In python 3.x, the zip function itself runs in O(1)
time, as it just allocates a special iterable (called the zip object), and assigns the parameter array to an internal field. The function invocation itself (before control reaches in zip) is O(N)
, as the interpreter must convert the parameters to an array. Every subsequent next
call on the iterator also runs in O(N)
. Exhausting the zip object is therefore O(N*M)
assuming M is the average (or minimum) length of the iterables, excluding the time the iterables themselves take to generate items (as it is independent of zip).
在 python 2.x 中,zip 函数返回一个列表.该列表必须在调用期间构建,这等效于耗尽前面示例中的迭代器,因此 O(N*M)
,不计算在压缩的迭代器中花费的时间.
In python 2.x, the zip function returns a list. That list must be constructed during the call, that is equvivalent to exhausting the iterator in the previous example, so O(N*M)
, not counting the time spent in the zipped iterables.
这篇关于Python 中 zip() 的时间复杂度是多少?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
更多推荐
[db:关键词]
发布评论