Python中整数比较的时间复杂度

Question

Python中整数比较的时间复杂度如何？例如，如果我们使用两个函数计算1000的阶乘，然后检查相等性，它的时间复杂度是O(1)吗？

def fact(n):
    prod = 1
    for i in range(n):
        prod = prod * (i + 1)
    return prod

i = fact(1000)
j = fact(1000)

# Complexity of this check?
if i == j:
    print "Equal"

- ayushgp

---

使用我的Python 2.7.12版本时，出现了一个错误：RuntimeError: maximum recursion depth exceeded。 - Louis

@Louis 请在这里查看：http://www.codeskulptor.org/#user43_6wTA8XtBGQ_0.py - ayushgp

@ayushgp CodeSkulpter并不是自己的Python实现。它是专门为Rice大学的一门课程而制作的。它的行为不像通常的Python（即CPython），因此人们会因为你的代码而出现“最大递归深度”错误。 - juanpa.arrivillaga

我已经编辑了代码，仅侧重于我提出的问题。 - ayushgp

Answer 1

这并不是一个简单的问题，但答案却很明显 ;-)

也就是说，如果两个整数确实相等，那么在不比较所有位的情况下是不可能知道的。因此，在相等情况下，所需的时间与位数成正比（如果N是比较对象之一，则成比例于log(abs(N))）。

如果它们实际上并不相等，则有几种情况，都与实现内部相关。长整数以2的幂次方作为基数存储为“数字”向量。如果这些向量长度不同，则这些整数不相等，并且这需要常量时间。

但是，如果它们具有相同长度，则必须比较“数字”，直到找到第一个（如果有）不匹配的对。这需要花费与需要比较的数字数量成正比的时间。

然后将所有上述内容复杂化以考虑可能的符号混合。

- Tim Peters

---

你所说的N是什么并不是很清楚，而且你似乎在同时比较O(N)和O(logN)。听起来好像有一个正确的答案，也许更容易的方法是只考虑特定情况，例如1000！== 1000！ - pvg

如果你正在比较 N == M 并且它们相等，那么所需的时间与 log(abs(N)) 成正比 - 与表达 N 所需的位数成正比。如果它们不相等，请再次阅读答案 ;-) - Tim Peters

为什么对两个相同的亿位比特序列进行顺序、穷举比较的时间复杂度是O(log(亿))? - pvg

不是这样的。如果你有两个相等的亿位比特序列，那么需要进行亿次比较才能知道它们是否相等。但是，如果你比较的是两个整数，每个整数都等于一亿，那么只需要进行log2(亿)次比较即可。 - Tim Peters

@TimPeters 好的，N 就是数字本身，这就是我想让你澄清的。 - pvg

@juanpa.arrivillaga 提出的“序列比较的时间复杂度”是个合理的问题，而“最坏情况性能”也是一个有意义的指标，尤其当这些序列恰好相同时。 - pvg