用O(n)内存代替O(n log n)的Karatsuba算法
已知具有时间复杂度~O(n^log2(3))的递归Karatsuba乘法算法比具有复杂度O(n^2)的简单乘法算法快。
但是，它使用的内存空间比“年级”算法-- O(n log(n))而不是O(n)内存--要大得多，对于拥有少量内存的控制器或非常小的计算机来说，这是非常关键的。
所以，我的问题是： 在karatsuba算法中有实现
O(n)内存空间的方法吗？
PS:我知道使用快速傅立叶变换你可以获得更快的速度O(n log(n))和更好的内存使用O(n)，但是我只是对Karatsuba很好奇。
回答 2
Stack Overflow用户
发布于 2015-05-04 14:49:09
Karatsuba算法只需要O(n)空间。
(A0 2^n + B0)(A1 2^n + B1)
= A0 A1 2^(2n) + B0 B1 + ((A0+B0)(A1+B1) - A0 A1 - B0 B1)2^n这里有一个粗略的归纳论点。归纳起来，假设使用Karatsuba算法乘法n位数只需cn空间.若要将2n -位数相乘，我们可以在cn空间中乘A0 A1，然后将答案保存在2n空间中，然后将B0 B1乘到cn空间中，然后将答案保存在2n空间中，然后在cn空间中乘(A0+B0)(A1+B1)。此时，我们最多使用(c+4)n空间。然后我们执行减法，并在4n空间中记录答案。峰值空间利用率为(c+4)n，小于最大(c，4)(2n)空间。所以，只要c>4，如果它用cn空间来乘n个数字，那么它就需要c( 2n )空间来乘2n个数字。这是不精确的，因为(A0+B0)和(A1+B1)可能有n+1数字而不是n。因此，严格的归纳论证更麻烦，但可以按照相同的基本模式进行。
这个问题的前提是错误的。Karatsuba乘法只需要O(n)空间，而不需要Omega(n log )。有些实现可能需要更多的空间，而不一定仅限于O(n log )，例如，如果您并行地进行计算。
事实上，在O(log )额外位中做Karatsuba乘法是可能的。
Stack Overflow用户
发布于 2019-04-03 14:37:32
https://stackoverflow.com/questions/30030490
复制相似问题
腾讯云开发者
