多进制数的乘法时间复杂度 O(n)?

[qwertyegg]

举个🌰，比如 7-5-3 进制数，可以表示 0-104 ，105 个整数

7-5-3 进制数跟 10 进制数的转换

0-0-0 表示 0 1-1-1 表示 1 2-2-2 表示 2 3-3-0 表示 3 4-4-1 表示 4 5-0-2 表示 5

以此类推

6-4-2 表示 104

10 进制数转换为 7-5-3 进制数很容易，求余即可。反过来，7-5-3 进制数转换为十进制数可用中国剩余定理算 a-b-c to (a15 + b21 + c*70) mod 105.

显而易见，7-5-3 进制数的加法:

a-b-c + x-y-z = (a+x)-(b+y)-(c+z)，只需要对每位计算一次，完全不需要考虑进位。当然这个并不是大问题，计算机算加法也是可以同时并行计算每一位，并不是手算那种需要考虑进位的依赖。

有意思的是乘法:

a-b-c * x-y-z = (ax) mod 7-(by) mod 5-(c*z) mod 3

n 位的乘法只需要 O(n)，而非小学学的 O(n^2)，也比基于 FFT 的 O(nlog n log log n)快

其中最大的优点是可并行计算，只要计算单元够多，O(1)就能计算出乘法结果而没有进位的依赖.

[qwertyegg]

前面一段排版有点问题，

0-0-0 表示 0

1-1-1 表示 1

2-2-2 表示 2

3-3-0 表示 3

4-4-1 表示 4

5-0-2 表示 5

[KeShih]

时间复杂度是一个渐进的概念，只考虑有限输入规模是没有意义的。只考虑限定输入大小时候，你会自然的把一些和输入规模相关的量当成常数，而得到一个错误的时间复杂度

目前 n-bit 整数相乘最快的算法时间复杂度是 O(n log n)，21 年发表在数学四大上
"Integer multiplication in time O(n log n)", Annals of Mathematics, 2021
论文地址： https://annals.math.princeton.edu/2021/193-2/p01

[murmurkerman]

写下你的算法测试下就好了，o(n)不太可能实现。

[msg7086]

另外提一句，时间复杂度是计算时间增量与输入量增量的关系，不是计算时间与输入量的关系。
O(n)并不见得会比 O(nlogn)快，只是说 O(n)对于 n 增加的时候，计算时间增加的速度比 O(nlogn)少。
可能有一种算法，复杂度是 O(n)，对于输入位数 10 的计算时间是 100 ，另一种算法，复杂度是 O(nlogn)，对于输入位数 10 的计算时间是 10log10 ，后者还是会比前者快。