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

问题描述

Python 中非常大整数的整数比较的时间复杂度是多少?例如，如果我们使用 2 个函数计算 1000 的阶乘，然后检查相等性，是否为 O(1)?

What is the time complexity of integer comparison in Python for very large integers? For example, if we calculate factorial of 1000 using 2 functions, then check equality, is it 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"

推荐答案

没有简单的答案，但答案很明显 ;-)

There isn't a simple answer, but the answer is nevertheless obvious ;-)

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

That is, if two integers are in fact equal, it's impossible to know that without comparing all their bits. So in case of equality, the time needed is proportional to the number of bits (which is proportional to log(abs(N)) if N is one of the comparands).

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

If they're not in fact equal, there are several cases, all related to implementation internals. Long ints are stored as a vector of "digits" in a power-of-2 base. If the vectors don't have the same lengths, then the ints aren't equal, and that takes constant time.

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

But if they do have the same lengths, then the "digits" have to be compared until finding the first (if any) mismatching pair. That takes time proportional to the number of digits that need to be compared.

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

Then complicate all the above to account for possible mixtures of signs.

这篇关于python中整数比较的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！