将从这篇博文开始记录coursera斯坦福算法专项课程的笔记，每一周的内容分为两个部分，课程内容回顾以及习题详解，下面进入正题。

附上课程地址：https://www.coursera.org/specializations/algorithms

Course 1 Week 1

第一门课主要是介绍分治算法的，这一周主要介绍了一些算法的基本概念，例如算法复杂度等等，下面分别回顾下。

整数乘法

  • Input: 两个数字n位的数字x,y
  • Output: x*y

如果直接计算不必多说，中学里已经学过，这里老师介绍了另一种算法

Karatsuba Multiplication

记$x =10^{\frac n 2}a+b,y=10^{\frac n 2}c+d$，那么

这样来看，我们只要计算$ac,ad,bc,bd$即可，考虑如下关系

这说明不必分别计算$ad,bc$，而是可以把这两项的和当作整体，通过计算$(a+b)(c+d),ac,bd$来计算出$ad+bc$，

所以就有了如下算法

  • $xy = 10^nac +10^{\frac n 2} (ad+bc) + bd$
  • 递归计算$ac$
  • 递归计算$bd$
  • 递归计算$(a+b)(c+d)$
  • 计算$ad+bc = (a+b)(c+d)-ac-bd$

这个算法是一个典型的分治算法，下面再介绍一个经典的分治算法——Merge Sort

Merge Sort

算法介绍

Merge Sort是用来排序的，之所以这里介绍它，是因为这个算法采取了分治的思路，先给出算法的输入输出

  • Input: n个数字的未排序数组
  • Output: 数组按递增顺序排列

再给出算法的伪代码

  • 递归地对数组的前一半进行排序
  • 递归地对数组的后一半进行排序
  • 将两个数组归并(merge)为一组

归并的伪代码如下

算法分析

有了算法，最重要的是分析它的运行效率，我们来讨论Merge Sort的时间复杂度。

先考虑每次merge的时间复杂度，假设merge的数组的长度为$m$，由上图可知，$i,j$初始化需要$2$次操作，后面每次循环分别需要$4$次，分别为给$k$赋值，比较$A(i),B(j)$，给$C(k)$赋值，$i,j$的自增运算，所以每次merge需要$4m+2 \le 6m$次操作。

接着考虑递归的过程，方便起见，假设原数组的长度$n$为$2$的幂。由伪代码可知，每次将数组均匀拆分为两个长度为原有数组长度一半的数组，所以这个过程最多进行$\text{log}_2n$次，整个过程可以由如下树状图所示：

考虑第$j$层，有$2^j$个节点，每个节点有$\frac{n}{2^j}$个数字，即第$j$层有$2^j$个子问题，每个子问题的大小规模为$\frac{n}{2^j}$，所以第$j$层merge所需的时间复杂度为

因为一共有$\text{log}_2n+1$层， 所以总共的时间复杂度为

最后，为了叙述方便，这里再介绍算法分析常用的一些符号。

常用记号

Big-Oh Notation

定义：

这里比较关键的一点是$c_,n_0$与$n$无关。

Omega Notation

定义：

这里也是$c_,n_0$与$n$无关。

Theta Notation

定义：

这也等价于

例子

这里举一个比较重要的例子

从两个方向证明

所以

因此