【算法设计与分析】概述（三）— <分析基础>

【背景】

        在概述（二）中，我们着重介绍了对$O$的分析，事实上还有很多关于复杂度的分析，以及重要结论，但眼下无论是工业界或是学界都着重分析$O$,篇幅有限我们在概述（二）中点到即止，详细的分析法还请查阅《计算机程序设计艺术》，本文针对$O$的分析回顾一下中学数学基础，方便今后对时间复杂度进行分析。

【标准记号与常用函数】

单调函数

单调递增：

$m\le n\Rightarrow f(m)\le f(n)$

单调递减：

$m\le n\Rightarrow f(m)\ge f(n)$

严格单调递增：

$m<n\Rightarrow f(m)<f(n)$

严格单调递减：

$m<n\Rightarrow f(m)>f(n)$

取整函数

向下取整：

$\lfloor x\rfloor$

向上取整：

$\lceil x\rceil$

取整函数若干性质

• $x–1<\lfloor x\rfloor \le x\le \lceil x\rceil <x+1$

• $\lfloor n/2\rfloor +\lceil n/2\rceil =n$

• 对于$n\ge 0,a,b>0$有：

$\lceil \lceil n/a\rceil /b\rceil =\lceil n/ab\rceil$

$\lfloor \lfloor n/a\rfloor /b\rfloor =\lfloor n/ab\rfloor$

$\lceil a/b\rceil leq(a+(b-1))/b$

$\lfloor a/b\rfloor \ge (a-(b-1))/b$

$f(x)=\lfloor x\rfloor ,g(x)=\lceil x\rceil \mathrm{为}\mathrm{单}\mathrm{调}\mathrm{增}\mathrm{函}\mathrm{数}$

多项式函数

• $p(n)=a_0+a_{1}n+a_2{n}^2+\cdots +a_d{n}^d;a_d>0$
• $p(n)=\mathrm{\Theta }(n^d)$
• $f(n)=O(n^k)\iff f(n)\mathrm{多}\mathrm{项}\mathrm{式}\mathrm{有}\mathrm{界}$
• $f(n)=O(1)f(n)\le c$
• $k\ge d\Rightarrow p(n)=O(n^k)$
• $k\le d\Rightarrow p(n)=\mathrm{\Omega }(n^k)$
• $k>d\Rightarrow p(n)=o(n^k)$
• $k<d\Rightarrow p(n)=\omega (n^k)$

指数函数

对于正整数$m,n$和实数a > 0

• $a^0=1$
• $a^1=a$
• $a^{-1}=\frac{1}{a}$
• $(a^m{)}^n=a^{mn}$
• $(a^m{)}^m=(a^n{)}^m$
• $a^m{a}^n=a^{n+m}$
• $a>1\Rightarrow a^n\mathrm{为}\mathrm{单}\mathrm{调}\mathrm{递}\mathrm{增}\mathrm{函}\mathrm{数}$
• $\begin{array}{r}a>1\Rightarrow \underset{n\to \mathrm{\infty }}{lim}\frac{n^b}{a^n}=0\Rightarrow n^b=o(a^n)\end{array}$
• $\begin{array}{r}{e}^x=1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\cdots =\sum _{i=0}^{\mathrm{\infty }}\frac{x^i}{i!}\end{array}$
• $e^x\ge 1+x$
• $|x|\le 1\Rightarrow 1+x\le e^x\le 1+x+x^2$
• $\begin{array}{r}\underset{n\to \mathrm{\infty }}{lim}(1+\frac{x}{n}{)}^n=e^x\end{array}$

对数函数

• $\log n={\log }_{2}n$
• $\lg n={\log }_{10}n$
• $\ln n={\log }_{e}n$
• ${\log }^{k}n=(\log n{)}^k$
• $\log \log n=\log (\log n)$

对所有实数$a>0,b>0,c>0,\mathrm{和}n$有：

• $a=b^{{\log }_{b}a}$
• ${\log }_c(ab)={\log }_{c}a+{\log }_{c}b$
• ${\log }_b{a}^n=n{\log }_{b}a$
• ${\log }_{b}a=\frac{lo{g}_{c}a}{lo{g}_{c}b}$
• ${\log }_b(1/a)=-lo{g}_{b}a$
• ${\log }_{b}a=\frac{1}{lo{g}_{a}b}$
• $a^{lo{g}_{b}c}=c^{lo{g}_{b}a}$
• $|x|\le 1\Rightarrow \ln (1+x)=x–\frac{x^2}{2}+\frac{x^3}{3}–\frac{x^4}{4}+\frac{x^5}{5}+\cdots +(-1{)}^{n-1}\frac{x^n}{n}$
• $forx>-1,\frac{x}{1+x}\le \ln (1+x)\le x$
• $\begin{array}{r}foranya>0,\underset{n\to \mathrm{\infty }}{lim}\frac{{\log }^{b}n}{(2^a{)}^{\log n}}=\underset{n\to \mathrm{\infty }}{lim}\frac{{\log }^{b}n}{n^a}=0\Rightarrow {\log }^{b}n=o(n^a)\end{array}$

阶乘函数

$n!=\{\begin{array}{ll}1& n=1\\ n(n-1)!& n>0\end{array}$

Stirling's approximation:

$n!=\sqrt{2\pi n}(\frac{n}{e}{)}^n(1+\mathrm{\Theta }(\frac{1}{n}))$

• $n!=o(n^n)$
• $n!=\omega (2^n)$
• $\log (n!)=\mathrm{\Omega }(n\log n)$
• $n!=\sqrt{2\pi n}(\frac{n}{e}{)}^n{e}^{{\alpha }_n}，\mathrm{其}\mathrm{中}\frac{1}{12n+1}<{\alpha }_n<\frac{1}{12n}$

【数列求和公式】

等差数列求和：

$S_n=\frac{(a_1+a_n)n}{2}=n{a}_1+\frac{n(n-1)}{2}d$

等比数列求和:

$S_n=\frac{a_1(1-q^n)}{1-q}=\frac{a_1–a_{n}q}{1-q}(q\ne 0)$

【非递归算法复杂性分析】

基础：

(1) for/while循环

    循环体内计算时间*循环次数；

(2) 嵌套循环

    循环体内计算时间*所有循环次数；

(3) 顺序语句

    各语句计算时间相加；

(4) if-else语句

    if语句计算时间和else语句计算时间的较大者。

一般步骤：

1. 决定用哪个(或哪些)参数作为算法问题规模的度量

    可以从问题的描述中得到。

2. 找出算法中的基本语句

    通常是最内层循环的循环体。

3. 检查基本语句的执行次数是否只依赖于问题规模

    如果基本语句的执行次数还依赖于其他一些特性，则需要分别研究最好情况、最坏情况和平均情况的效率。

4. 建立基本语句执行次数的求和表达式

    计算基本语句执行的次数，建立一个代表算法运行时间的求和表达式。

5. 用渐进符号表示这个求和表达式

    计算基本语句执行次数的数量级，用大O符号来描述算法增长率的上限。

例子：

解法1：算法的基本操作为:$m++$，$m$的初值为0， $m$的值即为执行次数.由于内循环从$2\ast n\sim n$,所以$i$的最大值满足$2i\le n$，即$i\le n/2$:

解法2：$n$为偶数, 外循环执行$n/2$次. 外循环$i=1$时, 内循环$j$从$2$变到$n$, 语句$m++$执行$n-1$次; $i=2$时, 内循环执行$n-3$次; ……; $i=n/2$时, 内循环执行1次.

故:

$m=(n-1)+(n-3)+\cdots +3+1=\frac{n^2}{4}$

即：

$T(n)=O(n^2)$

【递归算法复杂性分析】

基础：

对递归算法时间复杂性的分析, 关键是根据递归过程建立递推关系式, 然后求解这个递推关系式》

例1：

可得递推式：

$T(n)=\{\begin{array}{ll}1& n=0\\ T(n-1)+1& n>0\end{array}$

解之：

$T(n)=n$

例2：

可得递推式：

$T(n)=\{\begin{array}{ll}1& n=1\\ 2T(n-1)+1\end{array}$

解之：

扩展递归

扩展递归（extended recusion）是一种常用的求解递推关系式的基本技术，扩展就是将递推关系式中等式右边的项根据递推式进行替换，扩展后的项被再次扩展，依次下去，会得到一个求和表达式，然后可以借助求和技术进行求解。

例：求解下述递推式时间复杂性：

解：

简单起见：设$n=2^k$,将递推式进行扩展：

【概述小结】

算法与程序

1. 算法基本概念和性质

2. 算法描述方法

问题求解过程

算法复杂性分析

1. 算法复杂性基本概念

2. 算法复杂性的渐近性态

3. 算法渐近分析记号的定义和性质

4. 非递归算法和递归算法的复杂性分析

【参考文献】

• 2019年广西师范大学计算机与信息工程学院算法设计与分析课件[OL].李志欣教授.2019.01.01