算法时间复杂度分析

DreamSophon

算法分析与设计

1、非递归算法复杂性分析常见求和公式

==等差数列：==

\begin{aligned} \sum_{k=1}^n a_{k}  & = \frac{n}{2} \left( a_{1} + a_{n} \right) \\                                         & = n a_{1} + \frac{n(n-1)}{2} d \end{aligned}

推导：

\begin{aligned} \sum_{k=1}^n a_{k} & = a_{1} + \left(a_{1}+d\right) + \left(a_{1}+2d\right) + \dots+         \left(a_{1}+(n-1)d\right) \\ & = n a_{1} + \frac{n(n-1)}{2} d \end{aligned}

==等比数列：==

\sum_{k=0}^{n-1} a q^{k} = \begin{cases} na, \quad q = 1 \\ a \dfrac{1-q^n}{1-q}, \quad q \ne 1\\ \end{cases}

推导：

S = a + aq + aq^1 + aq^2 + \dots + aq^{n-1}

\begin{aligned} qS   & = aq + aq^1 + aq^2 + aq^3 + \dots + aq^{n} \\ & = S - a + aq^n \end{aligned}

(1-q)S = a \left( 1-q^n \right)

==调和级数：==

\sum_{k=1}^{n} \frac{1}{k}

推导（参考ChatGPT）：

第一步

使用积分近似和式

\int_{1}^{n} \frac{1}{x}\,{\rm d}x = {\rm ln}\,n

该积分给出了调和级数增长的主要部分

第二步

通过积分下的矩形法则进行比较，得到调和级数与这个积分的关系

调和级数的下界

\frac{1}{k} \ge \int_{k}^{k+1} \frac{1}{x}\,{\rm d}x

将这些小的积分加起来，得到

\sum_{k=1}^{n} \frac{1}{k} \gt \int_{1}^{n} \frac{1}{x}\,{\rm d}x

调和级数的上界

\frac{1}{k} \le \int_{k-1}^{k} \frac{1}{x}\,{\rm d}x

故有

\sum_{k=2}^{n} \frac{1}{k} \le \int_{1}^{n} \frac{1}{x}\,{\rm d}x

则

\sum_{k=1}^{n} \frac{1}{k} = 1+\sum_{k=2}^{n} \frac{1}{k} \le 1+\int_{1}^{n} \frac{1}{x}\,{\rm d}x

综上所述，该调和级数的部分和被夹在两个积分之间，它的逼近式为

\int_{1}^{n} \frac{1}{x}\,{\rm d}x \lt \sum_{k=1}^{n} \frac{1}{k} \lt 1+\int_{1}^{n} \frac{1}{x}\,{\rm d}x

计算积分结果，则可以得到

{\rm ln}\,n \lt \sum_{k=1}^{n} \frac{1}{k} \le 1+{\rm ln}\,n

精确的渐近展开式

欧拉-麦克劳林公式

\sum_{k=1}^{n} \approx {\rm ln}\,n + \gamma + \frac{1}{2n} - \frac{1}{12n^2} + O\left( \frac{1}{n^3}\right)

其中，$\gamma \,$是欧拉常数，约为0.5772。

==对数求和：==

\sum_{i=1}^{n} {\rm log}\,i

推导（参考ChatGPT）:

\begin{aligned} \sum_{i=1}^{n} {\rm log}\,i & = {\rm log}\,1 +{\rm log}\,2+ \dots +{\rm log}\,n \\ & = {\rm log}\,(1\cdot2\cdot3\cdot \dots \cdot n) \\ & = {\rm log}\,(n!) \end{aligned}

渐近近似：斯特林公式的渐近表达式

n! \approx \sqrt{2\pi n} \, (\frac{n}{e})^{n}

取对数后得

{\rm log}\,(n!) \approx n\, {\rm log}\,n - n + \frac{1}{2} {\rm log}\,(2\pi n)

2、对数的底数不影响算法的阶

==对数换底公式==

{\rm log}_a \,b = \frac{{\rm log}_c \,b}{{\rm log}_c \,a}

推导：

假设

{\rm log}_a \,b = x

即

a^x = b

将其转化为以$\,c\,$为底的对数表达形式，两边同时取以 $c$ 为底的对数

{\rm log}_c \left(a^x \right) = {\rm log}_c \,b

即

x\,{\rm log}_c \,a = {\rm log}_c \,b

则

x = \frac{{\rm log}_c \,b}{{\rm log}_c \,a}

代入 ${\rm log}_a \,b = x$ ，得

{\rm log}_a \,b = \frac{{\rm log}_c \,b}{{\rm log}_c \,a}

上课推导算式过程中所用到的一步变换

a^{{\rm log}_b \,n} = n^{{\rm log}_b \,a}

3、递归算法复杂性分析

$n$ 为表示问题规模的符号

==递归算法时间复杂度典型递推方程之一==

T(n) = \begin{cases} O(1)                         & n = 1 \\ aT(n-1) + f(n)  & n \gt 1 \end{cases}

当 $n \gt 1$ 时，

\begin{aligned} T(n) & = aT(n-1) + f(n) \\ & = a(aT(n-2) + f(n-1)) + f(n) \\ & = a(a(aT(n-3) + f(n-2)) + f(n-1)) + f(n) \\ & = \dots \\ & = a^{n-1}T(1) + \sum_{i=2}^{n}a^{n-i} f(i) \end{aligned}

（1）若取$a = 2$，$f(n) = O(1)$，汉诺塔问题

\begin{aligned} T(n) & = 2^{n-1}T(1) + \sum_{i=2}^{n} 2^{n-i}f(i) \\ & = 2^{n-1}T(1) + \left(2^0+2^1+\dots+2^{n-1}\right)O(1) \\ & = 2^{n-1}T(1) + \left(2^{n-1}-1\right)O(1) \\ & = O(2^n - 1) \end{aligned}

（2）若取$a = 1$，$f(n)=n-1$，插入排序最坏情况

\begin{aligned} T(n) & = 1^{n-1}T(1) + \sum_{i=2}^{n} 1^{n-i}f(i) \\ & = O(1) + \sum_{i=2}^{n} i-1 \\ & = O(1) + \frac{n(n-1)}{2} \\ & = O\left(n^2\right) \end{aligned}

==递归算法时间复杂度典型递推方程之二==

T(n) = \begin{cases} O(1)                         & n = 1 \\ aT \left(\dfrac{n}{b}\right) + f(n)  & n \gt 1 \end{cases}

其中 $b$ 表示将问题规模 $n$ 分成的份数，$a$ 表示选取其中几分继续进行递归操作

当 $n \gt 1$ 时

\begin{aligned} T(n) & = aT \left(\dfrac{n}{b}\right) + f(n) \\ & = a(aT \left(\dfrac{n}{b^2}\right) + f\left(\dfrac{n}{b}\right)) + f(n) \\ & = a(a(aT\left(\dfrac{n}{b^3}\right) + f\left(\dfrac{n}{b^2}\right)) + f\left(\dfrac{n}{b}\right)) + f(n) \\ & = \dots \\ & = a^{{\rm log}_b \,n} T(1) + \sum_{j=0}^{{\rm log}_b \,n-1} a^j\,f\left(\dfrac{n}{b^j} \right) \\ & = n^{{\rm log}_b \,a} T(1) + \sum_{j=0}^{{\rm log}_b \,n-1} a^j\,f\left(\dfrac{n}{b^j} \right) \\ \end{aligned}

（1）若$f(n) = c$

当 $a \ne 1$ 时

\begin{aligned} T(n) & = n^{{\rm log}_b \,a} T(1) + \sum_{j=0}^{{\rm log}_b \,n-1} a^j\,f\left(\dfrac{n}{b^j} \right) \\ & = n^{{\rm log}_b \,a} T(1) + \sum_{j=0}^{{\rm log}_b \,n-1}a^j\,c \\ & = n^{{\rm log}_b \,a} T(1) + c\,\frac{a^0\left( 1-a^{{\rm log}_b\,n} \right)}{1-a} \\ & = O\left(n^{{\rm log}_b\,a}\right) \end{aligned}

当 $a = 1$ 时

\begin{aligned} T(n) & = n^{{\rm log}_b \,a} T(1) + \sum_{j=0}^{{\rm log}_b \,n-1} a^j\,f\left(\dfrac{n}{b^j} \right) \\ & = T(1) + \sum_{j=0}^{{\rm log}_b \,n-1}c \\ & = T(1) + c\,{\rm log}_b\,n \\ & = O({\rm log}_b\,n) \end{aligned}

（2）若$f(n) = cn$

当 $a \lt b$ 时

\begin{aligned} T(n) & = n^{{\rm log}_b \,a} T(1) + \sum_{j=0}^{{\rm log}_b \,n-1} a^j\,f\left(\dfrac{n}{b^j} \right) \\ & = n^{{\rm log}_b \,a} T(1) + \sum_{j=0}^{{\rm log}_b \,n-1} a^j\,\dfrac{cn}{b^j} \\ & = n^{{\rm log}_b \,a} T(1) + cn\sum_{j=0}^{{\rm log}_b \,n-1} \dfrac{a^j}{b^j} \\ & = n^{{\rm log}_b \,a} T(1) + cn \dfrac{1-\left(\dfrac{a}{b}\right)^{{\rm log}_b \,n}}{1-\dfrac{a}{b}} \\ & = O(n) \end{aligned}

当 $a = b$ 时

\begin{aligned} T(n) & = n^{{\rm log}_b \,a} T(1) + \sum_{j=0}^{{\rm log}_b \,n-1} a^j\,f\left(\dfrac{n}{b^j} \right) \\ & = n T(1) + \sum_{j=0}^{{\rm log}_b \,n-1}{cn} \\ & = n T(1) + cn\,{\rm log}_b \,n \\ & = O(n\,{\rm log}_b \,n) \end{aligned}

当 $a > b$ 时

\begin{aligned} T(n) & = n^{{\rm log}_b \,a} T(1) + \sum_{j=0}^{{\rm log}_b \,n-1} a^j\,f\left(\dfrac{n}{b^j} \right) \\ & = n^{{\rm log}_b \,a} T(1) + \sum_{j=0}^{{\rm log}_b \,n-1} a^j\,\dfrac{cn}{b^j} \\ & = n^{{\rm log}_b \,a} T(1) + cn\sum_{j=0}^{{\rm log}_b \,n-1} \dfrac{a^j}{b^j} \\ & = n^{{\rm log}_b \,a} T(1) + cn \dfrac{1-\left(\dfrac{a}{b}\right)^{{\rm log}_b \,n}}{1-\dfrac{a}{b}} \\ & = n^{{\rm log}_b \,a} T(1) + cn \dfrac{1-n^{{\rm log}_b \,\left(\frac{a}{b}\right)}}{1-\dfrac{a}{b}} \\ & = n^{{\rm log}_b \,a} T(1) + cn \dfrac{1-n^{\left({\rm log}_b \,a - 1\right)}}{1-\dfrac{a}{b}} \\ & = n^{{\rm log}_b \,a} T(1) + c \dfrac{n-n^{{\rm log}_b \,a }}{1-\dfrac{a}{b}} \\ & = O\left(n^ {{\rm log}_b \,a }\right) \end{aligned}

cdyangjian

看不懂，

yj028

这些数学公式他认得我，我认不得他

qi1990

看不明白

DreamSophon

latex公式好难显示出来

Qinmuyi

公式怎么加载出来过一会就不见了

crystalZ

弄个离线版的附件试试

Ichigo015

怎么看着看着公式就加载不出来了

shaunkelly

图床没有弄好？

DreamSophon

Qinmuyi 发表于 2024-12-6 21:37
公式怎么加载出来过一会就不见了

我没有发过markdown格式的文件，这里的公式在markdown文件里都是正常显示的，但是不知道为什么发出来很不稳定，刷新一下有时显示有时不显示的