数据结构和算法分析

大$O$记号（big-O notation）（上界）

$T(n) = O(f(n)) \iff \exists \ c>0 ,当n >> 2 后，有T(n) < c\cdot f(n).$

与T(n)相比，f(n)更为简洁，但依然反映前者的增长趋势。

常系数可忽略：$O(f(n))\quad=\quad O(c\times f(n))$

低次项可忽略：$O(n^{a}+n^{b})\quad=\quad O(n^{a}),\quad a>b>0$

大$\Omega$记号 （下界）

$ T(n)=\Omega(f(n))\iff\exists\ c>0，当 n>>2 后，有 T(n) > c\cdot f(n).$

$\Theta$记号

$\begin{aligned}&\mathrm{T(n)=\Theta(f(n)~):}\&\exists c_{1}>c_{2}>0\text{,当 n}>>2\text{ 后,有 }c_{1}\cdotp f(n)>T(n)>c_{2}\cdotp f(n)\end{aligned}$

$O(1)$

• 常数复杂度：不含转向（循坏、调用、递归等）必顺序执行，即是$O(1)$

$O(\log^{\mathsf{c}}\text{n})$

• 对数$O(\log\text{n})$$lnn,|, lgn ,|, log_{100}n ,|, log_{2013}n$

• 常底数无所谓$\begin{array}{rcl}{\forall\mathrm{a},\mathrm{b}>0,\mathrm{log}{a}n}&{=\mathrm{log}{a}\mathrm{b}\cdot\mathrm{log}{b}n}&{=\Theta\left(\mathrm{log}{b}n\right)}\\end{array}$

换底公式：$\log_ab=\frac{\log_cb}{\log_ca}.$

• 常数次幂无所谓$\forall c>0,\mathrm{logn}^c=c\cdot\mathrm{logn}=\Theta(\mathrm{logn})$

• 对数多项式（ploy-log function）$123*\log^{321}n+\log^{105}(n^{2}-n+1)\quad=\Theta(\log^{321}n)$

• 这类算法非常有效，复杂度无限接近于常数$\forall\mathrm{c}>0,\mathrm{}\mathrm{}\mathrm{}\mathrm{logn}=\mathrm{~}O(n^{\mathrm{c}})$

$O\left(n^{c}\right)$

• 多项式（polynomial function）

  $a_{k}n^{k}+a_{k-1}n^{k-1}+\ldots+a_{1}n+a_{0}=O(n^{k}),\ a_{k}>0$

• 线性（linear function）：所有$O(n)$类函数

• 从$O(n)$到$O(n^2)$：编程习题主要覆盖范围

• 幂：$[(n^{2013}-24n^{2009})^{1/3}+512n^{567}-1978n^{123}]^{1/11}=0(n^{61})$

$O(2^n)$

• 指数（exponential function）（难解）

  $\forall\ c>1,\ \mathrm{n}^{c}=O(2^{n})$

$e^{n}=1+n+n^{2}/2!+n^{3}/3!+n^{4}/4!+\ldots $

• 从$O\left(n^{c}\right)$到$O(2^n)$，是从有效算法到无效算法的分水岭

2-Subset

【问题描述】：$S$包含$n$个正整数，$\Sigma S = 2m $;$S$是否有子集$T$,满足$\Sigma T = 2m ?$

【选举人制】各州议会选出的选举人团投票而不是由选民直接投票50个州加1个特区，共538票获270张选举人票，即可当选；但是若共有两位候选人，是否可能恰好各得269票?

直觉算法 : 逐一枚举S的每一子集，并统计其中元素的总和

定理：$|2^S| = 2^{|S|}=2^{n}$

亦即：直觉算法需要迭代$2^n$轮，并（在最坏情况下）至少需要花费这么多的时间——不甚理想

定理：2-Subset is NP-complete

NP-complete问题：就目前的计算模型而言，不存在可在多项式时间内回答此问题的算法。

增长速度

算法分析

复杂度分析主要方法

迭代：级数求和

递归：递归跟踪+递推方程

猜测+验证

级数

算术级数：与末项平方同阶

$T(n)=1+2+\ldots+n=n(n+1)/2=O(n^{2})$

幂方级数：比幂次高出一阶 $\boxed{\sum_{k=0}^{n}k^{d}{\approx}\int {0}^{n}x^{d+1}dx=\frac{1}{d+1}x^{d+1}\Big|{0}^{n}=\frac{1}{d+1}n^{d+1}=O(n^{d+1})}$

$T_{2}(n)=1^{2}+2^{2}+3^{2}+\ldots+n^{2}=n(n+1)(2n+1)/6=O(n^{3})$
$T_{3}(n)=1^{3}+2^{3}+3^{3}+\ldots+n^{3}=n^{2}(n+1)^{2}/4=~O(n^{4})$
$T_4(n)=1^4+2^4+3^4+\ldots+n^4=n(n+1)(2n+1)(3n^2+3n-1)/30=O(n^5)$

几何级数（a>1）:与末项同阶

$T_{a}(n)=a^{0}+a^{1}+\ldots+a^{n}=(a^{n+1}-1)/(a-1)\ =O(a^{n})$
$1+2+4+\ldots+2^{n}=2^{n+1}-1=O(2^{n+1})=O(2^{n})$

收敛级数：

$\begin{aligned}
&1/1/2+1/2/3+1/3/4+\ldots+1/(n-1)/n=1-1/n=O(1) \
&{1}+1/2^{2}+\ldots+1/n^{2}<1+1/2^{2}+\ldots=\pi^{2}/6=O(1) \
&1/3+1/7+1/8+1/15+1/24+1/26+1/31+1/35+\ldots=1=0(1)
\end{aligned}$

几何分布：$(1-\lambda)\cdot[1+2\lambda+3\lambda^{2}+4\lambda^{3}+\ldots]=1/(1-\lambda)=0(1),0<\lambda<1$

可能未必收敛，然而长度有限

$\begin{aligned}
&h(n)=1+1/2+1/3+\ldots+1/n=\Theta(\log n) \ 调和级数\
&log1 + log2 + log3 + … + logn = log(n!) = O(n1ogn)\ 对数级数
\end{aligned}$

Concrete Mathematics(书籍推荐)

循环与级数

for(int i = 0; i < n; i++) {
	for(int j = 0; j < n; j++)
        O1Operation(i,j);
}

算术级数：$\sum_{i=0}^{n-1}n=n+n+…+n=n*n=0(n^2)$

for(int i = 0; i < n; i++) {
	for(int j = 0; j < i; j++)
        O1Operation(i,j);
}

算术级数：$\sum_{i=0}^{n-1}i=0+1+…+(n-1)=\frac{n(n-1)}2=O(n^2)$

for(int i = 0; i < n; i++) {
	for(int j = 0; j < i; j += 2013)
        O1Operation(i,j);
}

算术级数：$O(n^2)$

for(int i = 0; i < n; i << = 1) {//i左移一位，乘以2
	for(int j = 0; j < i; j++)
        O1Operation(i,j);
}

几何级数：

$1+2+4+\ldots+2^{\lfloor\log_2(n-1)\rfloor}$
$=\sum_{k=0}^{\left\lfloor\log_2(n-1)\right\rfloor}2^k\quad(let k=1og_{2}i)$

$=2^{\lceil{log_2n}\rceil}-1=O(n)$

for(int i = 0; i < = n; i++) {
	for(int j = 1; j < i; j+=j)
        O1Operation(i,j);
}

几何级数：$\sum_{k=0}^n\lceil\log_2\mathrm{i}\rceil= O(\mathrm{nlogn})$

迭代与递归

迭代乃人工，递归方神通

To iterate is human, to recurse, divine.

分治算法

减而治之【Decrease-and-conquer】

• 为求解一个大规模的问题，可以将其划分为两个子问题：其一平凡，另一个规模缩减//单调性

• 分别求解子问题，由子问题的解，得到原问题的解

递归算法分析：

• 递归跟踪（recursion trace）分析

• 数组求和（线性递归）

  • 检查每个递归实例
  • 累计所需时间（调用语句本身，计入对应的子实例）
  • 其总和即算法执行时间

  sum(int A[], int n) {
  	return (n < 1) ? 0 : sum(A, n-1) + A[n-1];
  }//线性递归

• • 本例中，单个递归实例自身只需$O(1)$时间
  • $T(n)=O(1)*(n+1)=O(n)$

• 递推角度，为求解sum(A, n)，需

  • 递归求解规模为n-1的问题sum(A, n-1) // $T(n-1)$
  • 再累加上A[n-1] // $O(1)$
  • 递归基：sum(A, 0) // $O(1)$

• 递归方程：$T(n)=T(n-1)+O(1)$ // recurrence

• $T(0) = O(1)$ // base

• $\begin{array}{rcl}{\mathrm{T(n)-n=}}&{\mathrm{T(n-1)-(n-1)}}&{=}&{\ldots}\{=}&{\mathrm{T(2)-2}}\{=}&{\mathrm{T(1)-1}}\{=}&{\mathrm{T(0)}}\{\mathrm{T(n)=O(1)+n=~O(n)}}\\end{array}$

• 数组倒置

  • 任给一数组A[0, n]，将其前后颠倒

  • 统一接口：void reverse(int* A, int lo, int hi);

  //递归版
  if(lo < hi) { //问题规模的奇偶性不变，需要两个递归基
  	swap(A[lo], A[hi]);
  	reverse(A, lo+1, hi - 1);
  }
  else return; //base case
  //迭代精简版
  while(lo < hi)
      swap(A[lo++], A[hi--]);

分而治之【Divide-and-conquer】

• 为求解一个大规模问题，可以

• 将其划分为若干（通常两个）子问题，规模大体相当

• 分别求解子问题

• 由子问题的解，得到原问题的解

• 数组求和（二分递归）

sum(int A[], int lo, int hi) { //区间范围A[lo, hi]
	if(lo == hi) return A[lo];
    int mi = (lo + hi) > 1; //右移（/2）
    return sum(A, lo, mi) + sum(A, mi+1, hi);
} //入口形式为sum(A, 0, n-1)

$T(n) = 各层递归实例所需时间之和$

$\begin{array}{rcl}=&O(1)\times(2^0+2^1+2^2+\ldots+2^{\log n})\=&O(1)\times(2^{\log n+1}-1)=O(n)\end{array}$

每层总数构成以2为倍数的几何级数：与末项同阶

• 递推角度，为求解sum(A, lo, hi)，需

  • 递归求解sum(A, lo, mi)和sum(A, mi+1, hi) // 2*T(n/2)
  • 进而将子问题的解累加 //O(1)
  • 递归基：sum(A, lo, lo) //O(1)

• 递推关系：

  • $\mathrm{T(n)=2^*T(n/2)+0(1)}$
  • $T(1)=O(1)$

• 求解：

  $\begin{array}{rcl}\mathrm{T(n)}{=}&2^\mathrm{T(n/2)}+c_1\\mathrm{T(n)}+c_1{=}&2^(\mathrm{T(n/2)}+c_1){=}&2^{2*}(\mathrm{T(n/4)}+c_1)\&{=}&\ldots\{=}&2^{\log n}(\mathrm{T(1)}+c_1){=}&n^*(\mathrm{c_2}+c_1)\\mathrm{T(n)}{=}&(\mathrm{c_1}+c_2)\mathrm{n}-c_1{=}&O(\mathrm{n})\end{array}$

动态规划

fib():迭代：

解决方法A（记忆：memoization n.记忆化；备忘；记忆表）

将已计算过实例的结果制表备查

解决方法B（动态规划：dynamic programming）

颠倒计算方向：由自顶而下递归，改为自底而上迭代

f = 0; g = 1;//fib(0),fib(1)
while(0 < n--) {
    g = g + f;
    f = g - f;
}
return g;//O(n)

最长公共子序列LCS：递归

子序列(Subsequence)：由序列中若干字符，按原相对次序构成

最长公共子序列(Longest Common Subsequence):两个序列公共子序列中的最长者