Lecture 9

绪论

这一章节介绍的是divide-and-conquer multiplication，divide的意思是分开，conquer的意思是占据，控制，divide-and-conquer直译下来就是分开后控制，其实就是分而治之的意思，multiplication的意思是乘法。divide-and-conquer multiplication算法的主要核心思想就是分治，通过分治来简化各种较为复杂的乘法运算。

后面还介绍了有关FFT的知识点，因为我也是问了别人才弄懂的，不做过多赘述。

Integer Multiplication

首先讨论实数与实数(整型与整型，浮点型与浮点型)之间的运算：

之前提到过基础的运算加减乘除，左移右移等的复杂度都视作O(1)，这个O(1)不是说只做一次操作，而是相对于字节长度固定的整型(浮点型)而言，因为字节长度也就是位数固定，和位数相关的运算的复杂度也看做常数级。

例如加减运算和左移右移运算，如果限定的位数为n，需要依次对每一位进行运算和记录进位，所以复杂度为O(n)

int整型的位数为32，也就是说一次加法运算做的操作次数约为32个常数单位。

如果是两个二进制数的乘法，需要其中的一个二进制数对另一个二进制数的每一位逐步进行运算，然后将运算的结果进行错位的相加。每一位(乘法)运算的复杂度为O(n)，n位的运算的复杂度就为O(n²)，错位相加总共需要相加的位数为n*n=n²，根据前面的结论也可以得到复杂度为O(n²)，总结n位二进制数相乘的复杂度为O(n²)。

int整型的位数为32，也就是说一次乘法运算做的操作次数约为32*32=1024个常数单位。同样都为基础运算，相较于加减法和左右移位，乘法的复杂度就要高很多。这就是为什么在前面提到的哈希技术中，需要尽可能地将乘法和模运算用左移右移运算来代替。

上面是一般的二进制乘法，分治思想是考虑将大的问题分割成若干个子问题解决，用分治法来优化二进制乘法就是将n位的二进制数相乘看作一个规模为n的问题，将一个二进制数分割成前半的部分和后半的部分，前半和后半的部分分别进行计算，规模为n的问题不断地切割成若干个规模为n/2的问题。

伪代码和对应部分的时间复杂度如下：