算法分析

佚名 5年前 (2019-03-20) 算法 871人围观抢沙发百度已收录

算法分析学习笔记

要学习算法设计，首先要学会分析算法，也就是明白怎么样去判断一个算法的好坏。算法分析一般首先从算法的时间复杂度开始着手分析，本文也将以时间复杂度的分析为主进行。

数学基础

公式1：\(T(n) = \sum_{i=1}^mt_i*e_i(n)\)
- m：m种元运算
- \(e_i\)：每种元运算执行次数\(e_i\)
- \(t_i\)：每种运算执行的时间\(t_i\)
函数渐近的界：
\(\lim_{n\to\infty}\frac{T(n)-T'(n)}{T(n)}=0\)，则\(T'(n)\)为\(T(n)\)在\(n\to\infty\)的渐近态
上界与下界：
- \(f(n)=O(g(n))\)，\(f(n)\)的渐近上界是\(g(n)\longleftrightarrow\exists c>0,n_0>0,\)使\(\forall n\ge n_0,\)有\(0 \le f(n) \le cg(n)\)
- \(f(n)=\Omega (g(n))\)，\(f(n)\)的渐近下界是\(g(n)\longleftrightarrow\exists c>0,n_0>0,\)使\(\forall n\ge n_0,\)有\(0 \le cg(n) \le f(n)\)
高阶与低阶
- \(f(n)=o(g(n))\)，\(f(n)\)当n充分大，比\(g(n)\)低阶\(\longleftrightarrow \forall c>0, \exists n_0 \in N \ \ when \ \ n \ge n_0, 0 \le f(n) \le cg(n)\)
- \(f(n)=\omega(g(n))\)，\(f(n)\)比\(g(n)\)高阶\(\longleftrightarrow \forall c>0, \exists n_0 \in N \ \ when \ \ n \ge n_0, 0 \le cg(n) \le f(n)\)
- \(f(n)=\Theta(g(n))\)，\(f(n)\)与\(g(n)\)同阶，\(g(n)\)是\(f(n)\)渐近紧的界\(\longleftrightarrow f(n)=O(g(n)) \land f(n)=\Omega(g(n))\)
传递性
- \(f=O(g),g=O(h) \longrightarrow f=O(h)\)
- \(f=\Omega(g),g=\Omega(h) \longrightarrow f=\Omega(h)\)
- \(f=\Theta(g),g=\Theta(h) \longrightarrow f=\Theta(h)\)
定理2：
\(f=O(h),g=O(h) \longrightarrow f+g=O(h)\)
多项式函数：
\(f(n)=a_0+a_1n+...+a_kn^k,a_k \ne 0\)有\(f(n)=\Omega(n^k),f(n)=O(n^k) \longrightarrow f(n)=\Theta(n^k)\)
对数函数
- \(a^{log_bn}=n^{log_ba}\)
- \(log_an=\Theta(log_bn)\)
两个低阶：
- \(\forall b>1,\forall a>0, has \ \ log_bn=o(n^a)\)
- \(\forall a>1,\forall k>0, has \ \ n^k=o(a^n)\)
常用公式：
- \(L'H\hat{o}spital's \ \ rule:\lim_{n\to\infty}\frac{f(n)}{g(n)}=\lim_{n\to\infty}\frac{f'(n)}{g'(n)}\)
- \(Stirling's \ \ aproximation:n!=\sqrt{2\pi n}\big(\frac{n}{e}\big)^n(1+\Theta(\frac{1}{n}))\)
函数阶的比较：
- \(\lim_{n\to\infty}\frac{f(n)}{g(n)}=c>0\longrightarrow f(n)=\Theta(g(n))\)
- \(\lim_{n\to\infty}\frac{f(n)}{g(n)}=0\longrightarrow f(n)=o(g(n))\)
- \(\lim_{n\to\infty}\frac{f(n)}{g(n)}=+\infty\longrightarrow f(n)=\omega(g(n))\)
阶乘的几个结论：
- \(n!=o(n^n),n!=\omega(2^n),log(n!)=\Theta(nlogn)\)
求和级数的基本法则：
- \(\sum_{k=1}^{n}ca_k=c\sum_{k=1}^na_k\)
- \(\sum_{k=1}^n(a_k\pm b_k)=\sum_{k=1}^na_n \pm \sum_{k=1}^nb_k\)
常见级数求和：
- 等差数列：\(\sum_{k=1}^na_n=\frac{n(a_1+a_n)}{2}\)
- 等比数列：\(\sum_{k=0}^naq^k=\frac{a(1-q^n)}{1-q}\)
- 调和级数：\(\sum_{k=1}^n\frac{1}{k}=lnn+O(1)\)
- 平方和：\(\sum_{k=1}^n=\frac{n(n+1)(2n+1)}{6}\)
用于递归求解的公式：
- 主定理：对\(a\ge 1,b>1,f(n)\)有\(T(n)=aT(\frac{n}{b})+f(n)\)，则
  - \(f(n)=O(n^{log_ba-\varepsilon}),\varepsilon >0,T(n)=\Theta(n^{log_ba})\)
  - \(f(n)=\Theta(n^{log_ba}),T(n)=\Theta(n^{log_ba}logn)\)
  - \(f(n)=\Omega(n^{log_ba+\varepsilon}),\varepsilon >0 \land c<1,n\ is \ big \ enough,has\ af(\frac{n}{b})\le cf(n) \longrightarrow T(n)=\Theta(f(n))\)
- 另一种情况：\(T(n)=aT(\frac{n}{c})+O(n)\)
  - \(T(n)=O(n),a<c\land c>1\)
  - \(T(n)=O(nlogn),a=c\ and\ c>1\)
  - \(T(n)=O(n^{log_ca}),a>c\ and\ c>1\)

两种算法的分析思路

非递归算法的分析

时间复杂度仅依赖于问题规模
1. 找到核心操作
2. 建立和式，并求解
时间复杂度还依赖于输入的初始状态
- 要讨论最好和最坏的情况下的时间复杂度。
- 用加权平均值作为平均时间复杂度，如果问题没有直接给出各个情况的可能性，而且我们无法证明他们的概率不同时，可以假设各个情况的可能性是相等的。

递归算法的分析

递推公式的建立
边界的确定
解递推式
注：当主定理失效时，可以使用递归树

实践

非递归问题

仅依赖于问题规模的时间复杂度

交换i与j的内容
C temp = i; i = j; j = temp;
核心操作是三个赋值语句。
和式：T(n)=3=O(1)
这个问题与问题的规模n无关，时间复杂度是常数阶的，T(n)=O(1)。
循环次数直接依赖于规模n

    x = 0;
    y = 0;
    for(k=1;k<=n;k++)
        x = x + 1;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            y = y + 1;

总共有两个循环，循环不变式分别是：`x=x+1`和`y=y+1`一般选择循环次数最多的当作核心语句，这里可以选择`y = y + 1`，和式是：$T(n)=2+2+\sum_{k=1}^{n}3+2+\sum_{i=1}^{n}(2+2+\sum_{j=1}^{n}3)=4+3n+2+\sum_{i=1}^{n}(4+3n)=6+3n+(4+3n)n=3n^2+7n+6=O(n^2)$
事实上，我们发现，程序的时间复杂度主要取决于循环内部的核心语句，循环外的语句只是为和式增加了常数项，而循环内的语句个数（只要不是循环）其实只是改变了$n^k$的系数，所以上面的求和可以简化成：$T(n)=\sum_{k=1}^{n}1+\sum_{i=1}^{n}\sum_{j=1}^{n}1=n+n^2=O(n)$

循环次数间接依赖于规模n
C x = 1; for(i=1;i<=n;i++) for(j=1;j<=i;j++) for(k=1;k<=j;k++) x = x+1;
循环不变式是x=x+1
三层嵌套，直接列出和式：\(\sum_{i=1}^n\sum_{j=1}^i\sum_{k=1}^j1=\sum_{i=1}^n\sum_{j=1}^ij=\sum_{i=1}^n\frac{(1+i)i}{2}=\frac{1}{2}\big[\sum_{i=1}^ni+\sum_{i=1}^ni^2\big]=\frac{1}{9}(n^3+3n^2+2n)=O(n^3)\)
循环次数不是规模的多项式形式
C i = 1; while(i<=n) i = i*2;
循环不变式是：i=i*2
这样的情况并不方便求和，但是我们求和的目的就是找出核心语句的执行次数，所以这里只要抓住变量的值与循环次数之间的关系就方便解决了。
| i | 已经循环的次数 |
| - | - |
| 1 | 0 |
| 2 | 1 |
| 4 | 2 |
|...|...|
|2^k| k |
|...|...|
而到底循环了几次，显然与边界条件有关，当i刚刚过n时，循环结束，此时可以视为i=2^k=n+1，则k=log₂(n+1)，所以算法时间复杂度为O(logn)

算法时间复杂度还与输入的初始状态有关

查找算法是这类情况的典型例子，我们这里以顺序查找为例子进行说明
C a[0] = target; for(i=n;i>=0;i--) if(a[i]==target) return i;
这里只是为了分析，所以只给出了核心部分的代码（也就是循环的部分）。
我们会发现，不同的target会导致程序的循环次数不通，不像上面几种情况，我们无法找到一种通用的和式来表达核心语句的执行次数，所以在这种情况下，我们就需要分情况讨论。
最坏情况：显然，最坏的情况就是要查找的元素不存在于数组中，那么这时，程序会忠实地执行直到遇到了哨兵，根据前面的经验，很容易得知这时的时间复杂度是O(n)。
最好情况：想什么来什么是最好不过的情况了，a[n]就是要找的元素，那么最好情况下，核心语句只执行一次，时间复杂度是O(1)。
平均时间复杂度：之前说了，平均复杂度就是每种情况下时间复杂度的加权平均，而权值就是每种情况发生的概率，可惜的是，作为算法设计者和分析者，我们无法预测这个算法在实际运用中各个情况发生的概率，所以我们只好认为每种情况发生的可能是相同的。这里总共有n个元素再加上一种“找不到”的情况，我们可以列出下面的式子：
\(\sum_{i=0}^{n}\frac{1}{n+1}(n-i)=\frac{1}{n+1}(0+1+...+n)=\frac{n}{2}=O(n)\)

递归

想要明白递归，你首先要明白递归。这句话从一定的程度上展示了递归的形式，但是这是不完整的。
- 首先，这句话展示了递归最重要的特性——相同的形式。从代码的角度来说，就是函数调用了自己。
- 但是，这句话缺少了递归最重要的两点——问题规模的缩小、边界。这也就是为什么你按照上面那句话就永远不会明白递归的实质，但是在程序中递归却能解决问题。
  这两点确保了递归不会毫无限制的永远进行下去。
- 问题规模的缩小，在数学模型上的表现就是递推式，在保证问题的解决方式不变的前提下，要让问题的解决变简单。
- 边界就是递归终止的条件，这个条件在一定范围内是完全由人来决定的，就好像对于自然数是从0开始还是从1开始的争论一样——这完全取决于你的数学书上是怎么写的，但是你不能说它是从-1或者2开始的，因为“这不自然”。
求n!
- 这是再简单不过的问题了，用递归来实现甚至比你口算的过程还简单。
- 分析递归问题的关键就是递推式：n!=(n-1)!*n
- 我们假设递归边界是n=1，1!=1，很容易得到这样的式子：T(n)=T(n-1)+1，那个加一对应上面"*n"的操作。
- 现在一切都明了了，我们只要不停把上面的式子展开就行了，最后的答案一定是T(n)=n=O(n)。
主定理
- 上面只是最简单的递归，实际的递归程序往往要比这复杂得多，我们来看一个例子：T(n)=2T(n/2)+n，a=2,b=2,满足\(f(n)=n^2=\Omega(n^{log_ba})so\ T(n)=\Theta(nlogn)\)
递归树
- 拿T(n)=2T(n/2)+n来举例子，可以画出这样的树
  | sum=n | sum=n | ... |
  | - | - | - | - |
  | | n/2 | ... |
  | n | | |
  | | n/2 | ... |
- 树的每一层的和都是n，最长路径是log₂n，所以T(n)=O(nlogn)