我有以下函数:
def foo(length, num):
return num in range(length)
此函数的时间复杂度是多少?注意到range()
Python 3 上创建了一个 Range 对象,这个函数的时间复杂度是 O(1( 还是 O(N(?
想知道各种 Python 版本之间的时间复杂度是否存在差异(2 与 3(。
在python-3.x中,range(..)
是一个对象,它不构造一个列表。如果您使用int
作为项目执行成员检查,那么它可以非常快速地完成此操作。该算法有点复杂,因为有正步和负步。你可以在[GitHub]上查找它。对于x in range(a, b, c)
,具有正步数(c > 0
(的简单算法类似于:
x ≥ a ∧ x。
对于负步数(c < 0
(非常相似:
x ≤ a ∧ x> b ∧ mod(x-a, c( = 0。
如果我们考虑在O(1( 中进行比较并计算模数,则它是O(1(算法。实际上,对于巨大的数字,它缩放了数字的位数,因此它是一种O(log n(算法。
但是,这仅适用于int
秒。事实上,如果您使用float
s、complex
、其他数字或非数字类型,它不会执行上述计算。然后,它将回退到迭代range(..)
对象。这当然需要相当长的时间。如果你有一个一百万个元素的范围,它将因此迭代所有这些元素,最终到达范围的末尾,并返回False
,或找到匹配项,并返回True
。将来,也许可以为某些数值类型实现一些额外的功能,但通常不能这样做,因为您可以使用工作方式不同的相等运算来定义自己的数值类型。
在python-2.x中,range(..)
是一个返回列表的函数。事实上:
>>> range(15)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
>>> type(range(15))
<type 'list'>
为了检查元素是否是列表的成员,它将遍历列表,并检查所有项目的相等性,直到找到相等的元素或列表用尽为止。如果我们考虑检查两个项目是否等于常量时间,那么这需要线性时间O(n(。实际上,对于大数,检查两个数字是否相等,与"数字"的数量成线性关系,因此O(log m(与m表示该数字的值。
python-2.x 也有一个xrange(..)
对象,但这不会检查上述演示技巧的成员资格。