"really big int" 在时间复杂度和基本算术运算方面意味着什么

Question

我了解到基本的算术运算是在常数时间内执行的 O(1) 除非操作数“非常大”。所以我尝试了这个期望 via_str_method 会在达到某个边界时执行得更快：

import time
import math

start_time = time.time()


class OddNumbers:

    ODD_ONES = ["1", "3", "5", "7", "9"]

    def __init__(self, n):
        assert type(n) == int
        self.n = n
        self.str_n = str(n)

    def via_str_method(self):
        return True if self.str_n[-1] in self.ODD_ONES else False

    def via_mod_method(self):
        return True if self.n % 2 != 0 else False


n = int(math.pow(2, 1023))
odd_one = OddNumbers(n)

if odd_one.via_str_method():
    print("Number is ODD")
else:
    print("Number is EVEN")

str_end_time = time.time()
print(f"STR method time: {str_end_time - start_time}")

if odd_one.via_mod_method():
    print("Number is ODD")
else:
    print("Number is EVEN")

print(f"MOD method time: {time.time() - str_end_time}")

但即使使用 2**1023（我认为“足够大”），这两种方法仍然在恒定时间内执行。我想知道是否有人可以向我解释什么是“真正的大 int”，以及如何生成一个并在代码中使用它。

Answer 1

在第一种方法中，您使用索引从 self.str_n 中获取一个字符。索引访问是常数时间。接下来检查它是否在列表 ODD_ONES 中。搜索列表是线性时间，但是 ODD_ONES 是固定长度的，与 n 无关。因此这也是常数时间。

在第二种方法中，您检查是否可以被 2 整除。无论数字有多大，单位位置的数字决定了整除性。因此，这又是常数时间。

Python（以及任何其他主流语言）背后的人都是非常聪明的人；）

"really big int" 在时间复杂度和基本算术运算方面意味着什么

What does "really big int" mean in terms of time complexity and basic arithmetic operations

python

big-o

time-complexity