范围（）上的Python“in”运算符时间复杂度

Question

我有以下功能：

def foo(length, num):
  return num in range(length)

这个函数的时间复杂度是多少？注意到range()在 Python 3 上创建 Range 对象，这个函数的时间复杂度是 O(1) 还是 O(N)？

想知道各种 Python 版本之间的时间复杂度是否也存在差异（2 对 3）。

Answer 1

在python-3.x 中arange(..)是一个对象，它不构造一个列表。如果您使用intas 项目执行成员检查，那么它可以非常快地完成。该算法有点复杂，因为有正步和负步。你可以在[GitHub]上查找。具有正步数 ( c > 0) for 的简单算法x in range(a, b, c)类似于：

x ≥ a ∧ x < b ∧ mod(xa, c) = 0。

对于负步数 ( c < 0) 非常相似：

x ≤ a ∧ x > b ∧ mod(xa, c) = 0。

如果我们考虑在O(1) 中进行比较并计算模数，则它是O(1)算法。实际上，对于大数字，它会按数字的位数进行缩放，因此它是一个O(log n)算法。

然而，这仅适用于ints。实际上，如果您使用floats、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(..) 对象，但这不会使用上面演示的技巧检查成员资格。