Python 中 zip() 的时间复杂度是多少? [英] What is the time complexity of zip() in Python?

问题描述

如何计算 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屋！