引言
在CS170中，我们将学习图算法、贪婪算法、动态规划、线性规划、快速矩阵乘法、傅立叶变换、数论、复杂性和NP-完备性等算法的设计和分析。本节主要是课程介绍和算数的效率问题。
算法
An algorithm is just a well defined procedure for carrying out some computational tasks.
什么是算法？算法只是一个定义好的程序以便执行一些计算任务。
- Halts
- Correctness
- Efficiency
我们想从算法这门课中得到什么？我们希望我们的算法首先是有终点的；我们希望算法是正确的，当它终止时它能给出正确的输出；我们还想要追求效率，效率可以用许多不同的方法来衡量：我想要的是时间效率，就像我想让我的代码快速运行一样，我想尽快得到答案；我想要节约内存，不要使用太多的内存；如果我有一个并行算法我希望不要使用太多的并行机……所以一些运算资源例如时间、内存、并行性、随机性，我想尽量减少对运算资源的消耗。
加法
Today,Algos for arithmetic
Addition: How is input described?
Numeral system: ql-kwhorizmi popularized “Araboc” (further popularized by Fibonacci)
今天我们主要关注算术算法，第一个题目是加法。首先如何描述输入，有很多不同的数字系统比如罗马数字等等，对于进行算术运算非常不便，更方便的是阿拉伯数字系统，由Ql-kwhorizmi推广但在印度发明，后来通过斐波那契来进一步推广。
数手指
Input: two integers x,y given each as string of digits in base 10
Ex：5 + 7
Alg1：”count on hands” start at x,increment y times
现在我们很熟悉这个规则，加法的输入是两个整数x和y，每个都是以10为底的数字。
让我们思考不同的加法算法，大多数人第一种算法是什么？回想一下在儿时学过的算法，当你第一次学习数字的时候：数自己的手指，我真正关注的是从x开始，执行y次。
Runtime：x,y are each <= digits
time <= y * n = $10^n$ * n
这是一个正确的算法，但它的效率如何呢？当我说到效率的时候我的意思是运行时的效率，要花多少时间。所以对于运行时间，我要用x和y的位数来衡量它。假设x和y的长度为n位或者说每一个都有n个数位那么长，如果其中一位更短，我可以给它加上0假装它是n位。
我写下了x，然后递增它，增加一个n位数需要多长时间？最坏情况n，我可能可以侥幸没有任何进位，它就是常数时间；但最坏的情况是我需要n个时间步来增加一个位数：Y次，最多是y增量，每一次花费n时间。如果我想用n来表示输入的大小来理解运行时间，我可以说在最坏的情况下y为指数，也就是$10^n$，那么算法1的运行时间就是10的n次方乘以n。
如果我们仔细推导一下可能不会需要一个额外的n系数，实际上运行时间更像是10的n次方。但10的n次方已经很糟糕了，即使这是一个正确的算法，但它并没有那么快。
加法运算
Alg2：Addition
Runtime：n
幸运的是我们都知道另一种算法，并且这是我们在幼儿园就学了的算法：只要把一个数字写在另一个的上面，从右到左计算然后一直记录进位，然后我们就可以得到答案。
这个算法的运行时间是多少？n步。所以当你在设计算法的时候，你需要考虑的一点是我能做得更好吗？前一个算法需要$10^n$步，现在我们只需要n步就好了。
乘法
累加
Multiplication
Alg1：Add in x,y times
Time：y * n <= $10^n$ * n
这里有很多算法，算法一是加x y次。从0开始，加y次x到计数器上，将x添加到运行计数器需要多长时间？你运行的计数器总是在0和最终结果之间，如果用n位数乘以n位数，答案最多是2n位数，而每一次加法都需要n的时间，然后做y次。
乘法运算
Alg2：Multiplication
Time：$O(n^2)$
这不是我们通常使用的算法，我们通常用小学学到的乘法法则：从右边开始相乘，然后轮流乘最后把它们合到一起再加得到最后的结果。这里的大O可以想象成不会一直记录的隐藏变量。
Karatsuba算法
一个很自然的问题是你可以运算的更快吗？俄国数学家柯尔莫哥洛夫认为没有比$n^2$更快的算法了，但他被证明是错的，有人想出了一个比n平方还快的算法：分治算法。
Alg3：Divide & Conquer
$x = 5143 \qquad y = 0291$
$x_h = 51 \qquad x_l = 43 \qquad y_h = 02 \qquad y_l = 91$
$x = x_h * 10^{n/2} + x_l \qquad y = y_h * 10^{n/2} + y_l$
$xy=x_hy_h10^n+(x_hy_l+x_ly_h)*10^{n/2}+x_ly_l$
x和y是n位数字，我需要递归地乘以两个n/2位数的数直至我们熟记的乘法表，最终次数为4。
$T(n) <= 4 T(\frac{n}{2}) + c*n \qquad n>1$
$T(n) = 1 \qquad\qquad\qquad\space\qquad n = 1$
我们有这个函数$T(n)$，但是它是什么样的呢？总的时间就是这四个递归调用的时间：
$Time per level = cn + 2cn(4c\frac{n}{2}) + 4n(4^2 * c * \frac{n}{4}) + 8cn$
$Total = cn * (1+2+2^2+2^3+…+2^k)$
Done when $\frac{n}{2^k}=1 \to n = 2^k \to k = \log_2n$
在我得到基本情况前，k就是这个树的深度。当$\frac{n}{2^k}=1$时完成，这意味着k等于$\log_2n$。
$S = 1 + p + p^2 +p^3 + … + p^k$
$p*S = p + p^2 + p^3 + … +p^{k+1}$
$p * S - S = S * (p - 1) = p^{k+1} - 1$
$S = \frac{p^{k+1}-1}{p-1}$
$Total time = cn \frac{2^{\log_2n+1}-1}{2-1} = cn(2n-1) = O(n^2)$
所以我们的总时间为$O(n^2)$，所以我们实际上已经做完了所有的运算，这是比我们在小学学到的更复杂的版本。事实上它会更慢，因为递归需要时间，需要将参数推入调用堆栈。
$xy=x_hy_h10^n+(x_hy_l+x_ly_h)*10^{n/2}+x_ly_l$
回到之前的分治，理论上我们需要四个乘积。Coma Groves的朋友意识到我其实不需要这两个乘积，因为最后我会把它们加进去，我需要的是它们的和而不是每个单独的数字。有没有一种方法可以不用逐个运算就求出它们的和？他的灵感来自于高斯的一个快速乘法技巧：
$A = x_h \times y_h$
$B=x_l \times y_l$
$D = (x_h+x_l)\times(y_h+y_l)$
看起来很奇怪，神奇之处在于$x_hy_l+x_ly_h$可以改写成$D-A-B$：
$x \times y=A+(D-A-B) + B= D$
现在我得到了新的递归式：$T(n)<=3T(\frac{n}{2})+cn$，这意味着我们只需要进行三次递归：
$Time per level = cn + \frac{3}{2}cn + (\frac{3}{2})^2cn + (\frac{3}{2})^3cn$
$Total = cn * (1+\frac{3}{2}+(\frac{3}{2})^2+(\frac{3}{2})^3+…+(\frac{3}{2})^k)$
我仍然从n个数字到n/2到n/4再到n/8，每次都会保有数字，降到一位数的所需次数是一样的，唯一改变的是我的子集少了：不是分四次，每次推下去都是三个分支。
$Total time = cn \frac{\frac{3}{2}^{\log_2n+1}-1}{\frac{3}{2}-1} = \frac{3}{2} * 2cn * (\frac{3}{2})^{\log_2n} = 3c * 3^{\log_2n} = 3c * n^{\log_23} = O(n^{1.585})$
当然小于n的平方。你可能会问自己这看起来很好，因为每个人都已经用了乘法很长一段时间，而老师从未提到过这种算法。在Java中有标准库实现大型数据类型，但是在python中我们甚至不需要使用大型数据类型，查看python源码就会发现它事实上是用整数做乘法的，也就是这个古怪的递归算法（如果位数大于70位）。