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

Question

对于非常大的整数，Python 中整数比较的时间复杂度是多少？例如，如果我们使用 1000 个函数计算 2 的阶乘，然后检查相等性，是 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"

Answer 1

没有一个简单的答案，但答案仍然是显而易见的;-(

也就是说，如果两个整数实际上相等，如果不比较它们的所有位，就不可能知道这一点。 因此，在相等的情况下，所需的时间与位数成正比(如果N是比较之一，则与log(abs(N))成正比(。

如果它们实际上不相等，则有几种情况都与实现内部有关。 长整数以 2 的幂为基数存储为"数字"向量。 如果向量没有相同的长度，则整数不相等，这需要恒定的时间。

但是，如果它们确实具有相同的长度，则必须比较"数字"，直到找到第一个(如果有的话(不匹配对。 这需要与需要比较的位数成正比的时间。

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