25.11.24刷题日记——python内置默认大整数运算的用时开销陷阱
养眼一下）
在正式介绍之前，我们先看两端相同功能的代码：
代码1：
class Solution:
def prefixesDivBy5(self, nums: List[int]) -> List[bool]:
ans = []
temp = 0
for num in nums:
temp = temp * 2 + num
if temp % 5 == 0:
ans.append(True)
else:
ans.append(False)
return ans代码2：
class Solution:
def prefixesDivBy5(self, nums: List[int]) -> List[bool]:
ans = [False] * len(nums)
x = 0
for i, bit in enumerate(nums):
x = (x << 1 | bit) % 5
ans[i] = x == 0
return ans
上面两个程序其实都是leetcode的题目1018. 可被 5 整除的二进制前缀的正确解法，但是在测试集上的耗时却天差地别，代码1耗时138ms，代码2耗时3ms，那么是为什么呢？
结论：因为第一段代码中的 temp 不断变大，导致 Python 的大整数运算成本急剧上升；第二段代码始终保持 x < 5，计算量恒定，因此快 100 倍以上。
深度解析
▶ 第一段代码的性能问题：temp = temp \* 2 + num
随着读取更多 bit，temp 会越来越大，例如：
nums = [1,0,1,1,0,1,1,1,0,1,...]（长度1e5）此时 temp 代表当前前缀的二进制值，最后可以变成一个至少 3 万位以上的大整数。
在 Python 中，整数是 任意精度大整数，不是固定的 32bit 或 64bit。
因此，当 temp 很大时：
❗ 每次 temp * 2 都是 O(n) 时间复杂度
n = temp 的 bit 数（越来越大）。
举例：
| 当前 temp 的 bit 长度 | 一次乘 2 的耗时（大致） |
|---|---|
| 64 bit（8 bytes） | 快 |
| 1024 bit（128 bytes） | 变慢 |
| 100k bit（12.5 KB） | 很慢 |
| 1M bit（125 KB） | 非常慢 |
所以时间复杂度是：
O(1 + 2 + 3 + … + n) ≈ O(n²)（大整数累积开销）
▶ 第二段代码：x = (x << 1 | bit) % 5 始终保持 x ∈ {0,1,2,3,4}
关键就是：
⭐ x 每次都取 % 5，不会超过 4
所以 (x << 1 | bit) 也只在 0~9 之间，非常小，运算始终 O(1)。
对整个 nums 长度 N 的复杂度：O(N)
性能差异直观示例
假设 nums 长度 = 100000：
第一段代码
- temp 最终变成一个 100000 比特的超大整数
- 每次乘法都要处理越来越大的大整数
- 实际会到 几十毫秒甚至几百毫秒级
第二段代码
- x 全程 < 5
- 每次循环常数时间
- 实际只有约 0.5ms ~ 1ms
所以差了 100 倍非常正常。
在c++的算法实现中早已经有大整数的加减乘除相关的算法题，python具体的大整数的操作也是类似的，具体算法的关键词是高精度加减乘除，具体实现即是用数组列表去存对于的数字的每位，然后基于这个数组去模拟运算过程，加减法时间复杂度是O(N) ，乘除的时间复杂度是O(N^2)，这里N代表对应数组的长度。
相关题目链接：
P1601 A+B Problem（高精） – 洛谷
所以在我们使用python进行运算的时候，需要注意评估我们的中间临时变量的可能取值范围，适当在不影响算法结果的前提下需要取模控制数位长度。
