Python“输入"range() 上的运算符时间复杂度 [英] Python "in" operator time complexity on range()
问题描述
我有以下功能:
def foo(length, num):返回范围内的数量(长度)这个函数的时间复杂度是多少?注意到 range() 在 Python 3 上创建了一个 Range 对象，这个函数的时间复杂度是 O(1) 还是 O(N)?
想知道不同 Python 版本之间的时间复杂度是否也有差异(2 对 3).
在 python-3.x a range(..) 是一个对象，它不构造列表.如果您使用 int 作为项目执行成员检查，那么它可以非常快地完成.该算法有点复杂，因为有正步和负步.您可以在 [GitHub] 上查找.对于 x in range(a, b, c) 具有正步数 (c > 0) 的简单算法类似于:
x ≥∧×＜b∧mod(x-a, c) = 0.
对于负步数 (c <0) 非常相似:
x ≤∧×＞b∧mod(x-a, c) = 0.
如果我们考虑在 O(1) 中进行比较并计算模数，则它是一个 O(1) 算法.实际上对于大数字，它会按数字的位数进行缩放，因此它是一个 O(log n) 算法.
但这仅适用于 ints.实际上，如果您使用 floats、complex、其他数字或非数字类型，它不会执行上述计算.然后它会回退到迭代 range(..) 对象.这当然需要相当长的时间.如果您有一百万个元素的范围，它将因此迭代所有这些元素并最终到达范围的末尾，并返回 False，或找到匹配项，并返回 True.将来，也许可以为某些数值类型实现一些额外的功能，但一般情况下无法做到这一点，因为您可以使用工作方式不同的等式运算来定义自己的数值类型.
在 python-2.x, range(..) 是一个返回列表的函数.确实:
为了检查一个元素是否是列表的成员，它会遍历列表，并检查所有项目的相等性，直到找到一个相等的元素，或者列表已用完.如果我们考虑检查两个项目是否等于常数时间，那么这需要线性时间 O(n).实际上对于巨大的数字，检查两个数字是否相等，与数字"的数量成线性关系，所以 O(log m) 和 m 是那个数字的值.
python-2.x 也有一个 xrange(..) 对象，但这不会使用上面演示的技巧检查成员资格.
I have the following function:
def foo(length, num):
return num in range(length)
What's the time complexity of this function? Noting that range() creates a Range object on Python 3, will the time complexity of this function be O(1) or O(N)?
Would like to know whether there's a difference in time complexity between the various Python versions as well (2 vs 3).
In python-3.x a range(..) is an object, it does not construct a list. If you perform member checks with an int as item, then it can do that quite fast. The algorithm is a bit complicated, since there are both positive and negative steps. You can look it up on [GitHub]. A simple algorithm with a positive step count (c > 0) for x in range(a, b, c) is something like:
x ≥ a ∧ x < b ∧ mod(x-a, c) = 0.
For a negative step count (c < 0) is is quite similar:
x ≤ a ∧ x > b ∧ mod(x-a, c) = 0.
If we consider the comparisons to be done in O(1) and calculating the modulo as well, it is an O(1) algorithm. In reality for huge numbers, it scales in the number of digits of the numbers, so it is an O(log n) algorithm.
This however only works for ints. Indeed, in case you use floats, complex, other numerical or non-numerical types, it does not perform the above calculations. It will then fall back on iterating over the range(..) object. Which of course can take considerable time. If you have a range of a million elements, it will thus iterate over all these elements and eventually reach the end of the range, and return False, or find a match, and return True. In the future, perhaps some extra functionality can be implemented for some numerical types, but one can not do this in general, since you can define your own numerical type with an equality operation that works differently.
In python-2.x, range(..) is a function that returns a list. Indeed:
>>> range(15)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
>>> type(range(15))
<type 'list'>
In order to check if an element is a member of a list, it will iterate over the list, and check equality for all items until it finds an element that is equal, or the list is exhausted. If we consider checking if two items are equal to be constant time, then this takes linear time O(n). In reality for huge numbers, checking if two numbers are equal, scales linear with the number of "digits", so O(log m) with m the value of that number.
python-2.x has an xrange(..) object as well, but this does not check for membership with the above demonstrated trick.
这篇关于Python“输入"range() 上的运算符时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
