我有以下功能:
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]上查到. c > 0
的正步数 ( x in range(a, b, c)
) 的简单算法 类似于:
x ≥ a ∧ x < b ∧ mod(x-a, c) = 0。
对于负步数 (c < 0
) 非常相似:
x ≤ a ∧ x > b ∧ mod(x-a, c) = 0。
如果我们考虑在 O(1) 中完成比较并计算模数,则它是一个 O(1) 算法。实际上,对于巨大的数字,它会缩放数字的位数,因此它是一个O(log n) 算法。
但这只适用于 int
秒。事实上,如果你使用 float
小号,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(..)
对象也是如此,但这不会使用上面演示的技巧检查成员资格。
关于Python "in"range() 上的运算符时间复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/57929556/