"Algorithms"笔记 分治

summary

:

乘法

对于复数的乘法，我们是这样算的:

(a + bi)(c + di) = ac - bd + (bc + ad)i

但是，据说伟大的数学家高斯注意到的一个现象:

(bc + ad) = (a + b)(c + d) - ac - bd

这样，原来要进行ac, bd, bc, ad四次乘法，现在就只需要进行(a + b)(c + d), ac, bd 三次乘法，虽然多了几次加法，但是对于计算机来说，乘法计算远比加法慢，在数据量很大的情况 下，这个小技巧将会使算法性能得到极大的提升。