斯坦福算法专项课程Course1 week1内容回顾

将从这篇博文开始记录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

定义:

这也等价于

例子

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

从两个方向证明

所以

因此