算法基础

著名的图灵奖获得者Donald E. Knuth曾经说:"Computer science is the study of algorithm"，也就是计算科学就是研究算法的科学。这门学科主要的学习方法是通过经典算法的学习，积累经验，触类旁通，举一反三。

note

算法设计这门课学的是发现解决问题的算法，同时证明算法是正确、有效和能被接受的。不仅仅是找到答案，更要证明答案。通过例子来学习算法的思想，然后搬到其他问题中去解决其他问题。

什么是算法？(基本概念)

算法是解决某个问题的一系列运算或操作。编译器和操作系统就是典型的例子。算法问题主要包括输入和输出

• 输入:明确了算法能够接受的合法输入
• 输出:明确对于一组合法的输入，相应所得到的结果是什么

数学公式:$output = f(input)$，其中$f(\cdot)$就表示算法。

伪代码

伪代码是一种能够将标准运行的程序通过简介明了的语言进行描述，其特点是保持了程序原本主要的结构，类似C语言等。语法规则如下:

• 赋值:$\larr$
• 分支:if...then...else
• 循环:while,for,repeat...until
• 输出:return
• 调用:写函数名
• 注释: //...

特别注意！

需要特别注意的是，伪代码不能照搬原代码，需要进行部分精简，不需要具体的实现流程，只需要写出算法思路流程，分为哪几步，不用详细写这几步的实现过程，只需要使用自然语言或者相应的函数替代就行。忽略数据结构、模块、异常处理等。忽略变量的说明。

例子

Insert_Sort: 输入: $n$个元素的数组$A$; 输出: 按非降序排列的数组$A$;

for i <- 2 to n
  x <- A[i]
  j <- i - 1
  while (j > 0) and (x < A[j])
    A[j +  1] <- A[j]
    j <- j - 1
  A[j + 1] <- x
return A

算法复杂度

复杂度定义

算法的复杂度实际上是对算法执行次数的范围做一个估计。描述了一个算法执行次数至多和至少有多少，衡量一个算法的效率。描述的时候用到了高等数学中界的概念，一般有两种描述方式:

先设有任意正数$K_1$，使得有$f(n)\le K_1$，则称为$f(n)$的上界，记作$f(n)=O(K_1)$，其中$K_1=cg(n)$且存在正数$c$和$n_0$，对一切的$n\ge n_0$都成立。

同理，若任意正数$K_2$，使得有$f(n)\ge K_2$，则称为$f(n)$的下界，记作$f(n)=\Omega(K_2)$，其中$K_2=cg(n)$且存在正数$c$和$n_0$，对一切的$n\ge n_0$都成立。

如果，$f(n)=O(g(n))$且$f(n)=\Omega(g(n))$，则记作$f(n)=\Theta(g(n))$.

::: note O(g(n))与Ω(g(n))的含义

• $O(g(n))$表示该算法至多执行$g(n)$次（最多）
• $\Omega(g(n))$表示该算法至少执行$g(n)$次（最少）

本质上算法复杂度会这样表示是因为简化表示，比如现在有一个程序的复杂度为$n\log n + n - 2$，如果直接表示的话就是$f(n)=n\log n+n-2$，但这样表示不够方便，而且有很多不必要的元素，因为算法复杂度其实不需要一个很精确的表示，因为就算你表示得很精确又不能说明什么，何必多此一举；而且在某个区间上来说，$n\log n \ge n$那我既然都不用表示那么完整了，何必又要再写$n$和$2$？直接用最大的那个表示出来就可以了。所以就可以写成$O(n\log n)$.

1. 不需要精确表示
2. 不需要精确表示就可以对式子进行化简，留下最大那个
3. 为什么留下最大那个，因为他起主导作用 :::

函数的渐近的界

设$f_1(n)=O(g_1(n))$和$f_2(n)=O(g_2(n))$，则

1. $f_1(n)+f_2(n)=O(\max\{g_1(n), g_2(n)\})$
2. $f_1(n)\cdot f_2(n)=O(g_1(n)\cdot g_2(n))$

两种情况下的时间复杂度

1. 最坏情况下时间复杂度: 算法求解输入规模为$n$的算法所需要的最长时间$W(n)$
2. 平均情况下时间复杂度: 算法求解输入规模为$n$的算法所需要的平均时间$A(n)$
   $$A(n)=\sum_{I\in S}t_Ip_I$$
   其中，$S$:实例集, $t_I$:实例I基本操作次数, $p_I$: I的概率

note

复杂度表示的是针对问题选择基本运算，将基本运算的次数(输入规模)为自变量的函数。

• 也就是说，复杂度中的$n$表示算法的输入规模，经过$f(n)$次运算之后消耗的时间。本质上时间复杂度就是一个表示操作次数的边界的函数。

复杂度计算

• 例1

  $7n^2+6n+1=O(n^2)\\$ $7n^2\not =O(n) \\$ $\log n! =O(n\log n)(\log n=\log_2 n) \\$ $\log_a n=O(\log n)\\$ $2^{100}=O(1)$

• 例2

  $3n\log(n!)+(n^2+3)n\log n$

  $3n=O(n),\log(n!)=O(n\log n)\rArr 3n\log(n!)=O(n^2\log n) \\ (n^2+3)n=O(n^3),\log n=O(\log n)\rArr (n^2+3)n\log n=O(n^3\log n)$

  所以，$3n\log(n!)+(n^2+3)n\log n=O(\max\{n^2\log n, n^3\log n\})=O(n^3\log n)$

• 例3

  根据伪代码计算算法时间复杂度，每一行执行的操作的时间复杂度都要写上，有循环就用乘法，没有循环就用加法，将所有操作的时间复杂度加起来之后进行简化得到最终的时间复杂度。

递推方程求解

换元迭代

使用换元的方式对$n$进行处理。一般来说会用$n=2^k$进行换元。通过多此迭代套娃直到计算到$n=1$

• 例
  $$\begin{cases} W(n)=2W(\frac{n}{2})+n-1 \\ W(1)=0 \end{cases}$$
  令$n=2^k$，则有
  $$W(n)=2W(2^{k-1})+2^k-1 \\ =2[2W(2^{k-2})+2^{k-1}-1]+2^k-1 \\ =2^2W(2^{k-2})+2^k-2+2^k-1 \\ =2^2[2W(2^{k-3})+2^{k-2}-1]+2^k-2+2^k-1] \\ =... \\ =2^kW(1)+k2^k-(2^{k-1}+2^{k-2}+...+2+1) \\ =k2^k-2^k+1 \\ =n\log n-n+1$$

差消,化简迭代法

该法一般用于求解有比较复杂的式子的时候，通过作差消掉这些复杂项(复杂的项指的是那些求和符号之类的一些式子，跟正常纯字母的项不一样的)

• 例
  $$\begin{cases} T(n)=\frac{2}{n}\sum^{n-1}_{i=1}T(i)+O(n), n\ge2 \\ T(1)=0 \end{cases}$$
  $$T(n)=\frac{2}{n}\sum^{n-1}_{i=1}T(i)+cn^2, n\ge2 \\ nT(n)=2\sum^{n-1}_{i=1}T(i)+cn^2 (1)\\ (n-1)T(n-1)=2\sum^{n-2}_{i=1}T(i)+c(n-1)^2 (2)\\ nT(n)=(n+1)T(n-1)+O(n) (3)\\ \frac{T(n)}{n+1}=\frac{T(n-1)}{n}+\frac{c_1}{n+1}=...=c_1[\frac{1}{n+1}+\frac{1}{n}+...+\frac{1}{3}]+\frac{T(1)}{2} \\ =c_1[\frac{1}{n+1}+\frac{1}{n}+...+\frac{1}{3}]=\Theta(\log n)\\ T(n)=\Theta(n\log n)$$
  (1)(2)两式作差得(3)式

递归树

将子问题进行$b$等分,

主定理

设$a\ge1, b>1$为常数，$f(n)$为函数，$T(n)$为非负整数，且 $T(n)=aT(n/b)+f(n)=aT(n/b)+O(n^d)$

则有以下结果：

1. 若$f(n)=O(n^{\log_b a - \epsilon})$,$\epsilon>0$,那么$T(n)=\Theta(n^{\log_ba})(a>b^d)$
2. 若$f(n)=\Theta(n^{\log_ba})$,那么$T(n)=\Theta(n^{\log_ba}\log n)(a=b^d)$
3. 若$f(n)=\Omega(n^{\log_ba+\epsilon}),\epsilon>0$,且对于某个常数$c<1$和充分大的$n$有$af(\frac{n}{b})\le cf(n)$, 那么$T(n)=\Theta(f(n))(a<b^d)$

::: danger 特别重要! 从本质上来说，上面几条规则都是原式的$f(n)$与$n^{\log_ba}$比大小。

1. $f(n)<n^{\log_ba}$时，满足第一种情况
2. $f(n)=n^{\log_ba}$时，满足第二种情况
3. $f(n)>n^{\log_ba}$时，满足第三种情况 :::

• 例1:求解递推方程$T(n)=9T(\frac{n}{3})+n \\$ 上述方程中$a=9,b=3,f(n)=n$, 那么$n^{\log_39}=n^2\\ f(n)=n=O(n^{\log_39-1})=O(n)(\epsilon=1)$, 故满足第一种情况, $T(n)=\Theta(n^2)$
• 例2:求解递推方程$T(n)=T(\frac{2n}{3})+1$ 上述方程中$a=1,b=\frac{3}{2}, f(n)=1$, 那么$n^{\log_{\frac{3}{2}}1}=n^0=1 \\ f(n)=1=O(n^{\log_{\frac{3}{2}}1})=O(1)$, 故满足第二种情况, $T(n)=\Theta(n^0\log n)=\Theta(n\log n)$
• 例3:求解递推方程$T(n)=3T(\frac{n}{4})+n\log n$ 上述方程中$a=3,b=4,f(n)=n\log n$, 那么$n\log n=\Omega(n^{\log_43+\epsilon})=\Omega(n^{0.793+\epsilon})(\epsilon\approx0.2)$, 那么要使得$af(\frac{n}{b})\le cf(n)$成立，代入$f(n)=n\log n$, 得到$\frac{3n}{4}\log\frac{n}{4}\le cn\log n$, 不等式解得$c\ge\frac{3}{4}$，就可成立，满足第三种情况, 故得$T(n)=\Theta(f(n))=\Theta(n\log n)$.