3 函数的增长概念(中英对照)

本文主要是介绍3 函数的增长概念(中英对照)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

3.1 渐近记号

通过分析算法的时间复杂度 (Time complexity) 和空间复杂度 (space complexity) 来分析算法的效率。由此，引入了三种渐近记号 $\Theta ,O ,\Omega$ 其定义域为自然数集 $N=\left\{ 0,1,2,... \right\}$ 运行时间函数用T(n)来表示。

$\Theta (g(n))$ $\Theta$ 可简单记忆为 $" = "$
对于一个给定的函数g(n), 用 $\Theta (g(n))$ 来表示以下函数的集合:
$\Theta (g(n))=\left\{ f(n): 存在正常量c_{1}, c_{2}和n_{0},使得对所有n\geq n_{0},有0\leq c_{1}g(n)\leq f(n)\leq c_{2}g(n) \right\}$

$f (n) = O (g (n))$ $O$ 可简单记忆为 $\leq$
$O(g(n))=\left\{ f(n): 存在正常量c_{2}和n_{0},使得对所有n\geq n_{0},有 f(n)\leq c_{2}g(n) \right\}$

$f(n)=\Omega (g(n))$ $\Omega$ 可简单记忆为 $\geq$
$\Omega (g(n))=\left\{ f(n): 存在正常量c_{1}和n_{0},使得对所有n\geq n_{0},有0\leq c_{1}g(n)\leq f(n)) \right\}$

以上三种函数的图例如下：

3.1.1 用极限的方式理解三种渐近记号：

若 $\lim_{n\to+\infty} \frac{f(n)}{g(n)} =\infty$
此时 $f (n)$ 无限大 => $f(n)\geq cg(n) , f(n)=\Omega(g(n))$

若 $\lim_{n\to+\infty} \frac{f(n)}{g(n)} =0$
此时 $g (n)$ 无限大 => $f(n)\leq cg(n), f(n)=O(g(n))$

若 $\lim_{n\to+\infty} \frac{f(n)}{g(n)} =C (C 为非零常数)$
此时 $g (n)$ 无线接近f(n) => $f(n)=\Theta(g(n))$

3.1.2 时间复杂度的分析方法：
3.1.2.1、线性递归关系式 – Linear Recurrence Relations
表达式：
$a_{n} = c_{1}a_{n-1}+c_{2}a_{n-2}+...+c_{k}a_{n-k}+f(n)$
特点：
等号右侧为：

多项式 polynimial 从 $a_{n-1},...,a_{n-k}$
$c_{i}$ 常数系数 Constant coefficients
若 $f (n) = 0$ 为齐次方程 homogeneous equation
若 $f(n)\neq 0$ 为非齐次方程 Inhomogeneous equation

3.1.2.2、齐次常数系数 r阶方程的解题方法 linear homogeneous, constant coefficients, order k equations
$a_{n} = c_{1}a_{n-1}+c_{2}a_{n-2}+...+c_{k}a_{n-k}$
Step1: 建立特征多项式/Set the Characteristic equation
$r^k - c_{1}r^{k-1}-c_{2}r^{k-2}-...-c_{k}=0$
注： r 代表线性方程的根
Step2:计算此特征多项式的解得到多项式的根 r

Step3: 若所有根 r 是独特的(unique)
那么
$a_{n} = \alpha _{1}r_{1}^n +\alpha _{2}r_{1}^n +...+\alpha_{m}r_{m}^n$ , 且 $r_{1},r_{2},...,r_{m}$ 为不同的根(distinct roots)
若根 r 不是unique 的
那么我们有 t 个不同的根：每个根 $r_{i} 重复度为 m_{i}$ 且
$a_{n} = (\alpha _{10}+\alpha_{11}n+\alpha_{12}n^2+...+\alpha_{1m_{1}-1}n^{m_{1}-1})\color{red} r_{1}^{n}$
$+(\alpha _{20}+\alpha_{21}n+\alpha_{22}n^2+...+\alpha_{2m_{2}-1}n^{m_{2}-1})\color{red} r_{2}^{n}$
$+...+(\alpha _{t0}+\alpha_{t1}n+\alpha_{t2}n^2+...+\alpha_{tm_{t}-1}n^{m_{t}-1})\color{red} r_{t}^{n}$
Step4:使用初始条件计算 $\alpha_{i}$ or $\alpha_{ij}$

齐次线性方程的例题

Example 1:
已知： $a_{0}=2,a_{1}=7, a_{n} = a_{n-1}+2a_{n-2} 且n\geq2$

Step1: 建立特征多项式/Set the Characteristic equation
由 $a_{n} = a_{n-1}+2a_{n-2}$ 得到 k=2
Characteristic equation： $r^2 = r+2$

Step2: 解特征多项式
$(r - 2) (r + 1) = 0$
根 root 重复度multiplicity:
$r_{1} =2$ $m_{1}=1$
$r_{2}= -1$ $m_{2}=1$
注：由于所有根重复度为1 因此根都是unique的采用 $a_{n} = \alpha _{1}r_{1}^n +\alpha _{2}r_{1}^n +...+\alpha_{m}r_{m}^n$ 形式

Step3:
$a_{n} = \alpha_{1}2^n+\alpha_{2}(-1)^n$ ①

Step4:使用初始条件代入公式：
已知 $a_{0}=2,a_{1}=7$ 代入上述公式
$\alpha_{1}和\alpha_{2}$ 满足：
$f(x)=\left\{ \begin{aligned} \alpha_{1}\times2^0 +\alpha_{2}\times(-1)^0& = & 2\\ \alpha_{1}\times2^1 +\alpha_{2}\times(-1)^1 & = & 7& \end{aligned} \right.$
$\Leftrightarrow$
$f(x)=\left\{ \begin{aligned} \alpha_{1}+\alpha_{2}& = & 2 (n=0)\\ 2\alpha_{1} -\alpha_{2} & = & 7(n=1)& \end{aligned} \right.$
$\Rightarrow 得到\;\alpha_{1}=3\qquad\alpha_{2}=-1$ 代入到 ①
得到最终解为
$a_{n}=3\times2^n-(-1)^n$
Example2:
已知： $a_{n} = 2a_{n-1}-2a_{n-3}+a_{n-4} 删除线格式且n\geq4$ 且 $已知a_{0},a_{1},a_{2},a_{3}$
解： k=4
建立特征多项式characteristc equation: $r^4=2r^3-2r+1$
可写成 $\Rightarrow (r-1)^3(r+1)=0$
根 root 重复度multiplicity:
$r_{1} =-1$ $m_{1}=1$
$r_{2}= 1$ $m_{2}=3$
注：由于存在根重复度为3 因此根不是unique的，采用
$a_{n} = (\alpha _{10}+\alpha_{11}n+\alpha_{12}n^2+...+\alpha_{1m_{1}-1}n^{m_{1}-1})\color{red} r_{1}^{n}$
$+(\alpha _{20}+\alpha_{21}n+\alpha_{22}n^2+...+\alpha_{2m_{2}-1}n^{m_{2}-1})\color{red} r_{2}^{n}$
$+...+(\alpha _{t0}+\alpha_{t1}n+\alpha_{t2}n^2+...+\alpha_{tm_{t}-1}n^{m_{t}-1})\color{red} r_{t}^{n}$
Step4:使用初始条件计算 $\alpha_{i}$ $形式
General form of the solution:
$a_{n}=1^n\times(\alpha_{0}+\alpha_{1}n+\alpha_{2}n^2)+\alpha_{3}(-1)^n$
$=\alpha_{0}+\alpha_{1}n+\alpha_{2}n^2+\alpha_{3}(-1)^n$
利用已知的 $a_{0},a_{1},a_{2},a_{3}$ 解方程

Example3：初始条件已知 $a_{1},a_{2},a_{3}$
$a_{n}=a_{n-1}-a_{n-2}+a_{n-3}\;且n\geq4$
建立特征多项式 $r^3=r^2-r+1$
可写成 $\Rightarrow (r-1)(r+i)(r-i)=0$
根 root 重复度multiplicity:
$r_{1} =1$ $m_{1}=1$
$r_{2}= i$ $m_{2}=1$
$r_{3}= -i$ $m_{2}=1$
由于所有根重复度都为1，所以
$a_{n}=\alpha_{0}(i)^n+\alpha_{1}(-i)^n+\alpha_{2}1^n$
通过已知条件 $a_{1},a_{2},a_{3}$ 得到 $\alpha_{0},\alpha_{1},\alpha_{2}的值$
从而得到 $a_{n}$ 的最终形式

3.1.2.3、非齐次常数系数 r 阶方程
表达式：
$a_{n}=c_{1}a_{n-1}+c_{2}a_{n-2}+...+c_{k}a_{n-k}+f(n) 且有k个初始条件$
Step1:利用3.1.2.2中的方法解决齐次方程部分得到 $a_{n}^{(h)}$
假设
$a_{n}^{(h)}=c_{1}a_{n-1}+c_{2}a_{n-2}+...+c_{k}a_{n-k}$
不能用初始条件代入公式
Step2:找到f(n)的解 find a particular solution $\left\{ a_{n}^{(p)} \right\}$
Step3:得到 $a_{n}$ 的表达式: $a_{n}=a_{n}^{(h)}+a_{n}^{(p)}$ ①
Step4:利用初始条件代入① 得到 $a_{n}$ 的最终形式

在Step2找f(n)的particular solution时，有四种情况：

f(n)是多项式p(n) – $Cn^i$ 常数C乘 n 的 i 次方形式，i 为大于等于0的数
p(n)的次数等于f(n)的次数加 t
$d e g r e e (p (n)) = d e g r e e (f (n)) + t$
且如果在step1中存在根为1， t 等于根为1 的重复度。
否则 t=0 相当于在charactertistic equation 没有根的值等于 1
$f(n)=\beta^n且\beta为常数$
$a_{n}^{(p)}$ 为 $Cn^k\beta^n$ 的形式
且C是常数
若 $\beta$ 是characteristc equation 的根，那么k是 $\beta$ 的重复度
否则k=0
$f(n)=p(n)+\beta^n$ ，且 $p (n)$ 为多项式
将f(n)拆分为 $f_{1}(n)+f_{2}(n)$ 形式， $f_{1}(n)$ 用多项式方法解， $f_{2}(n)$ 用 $\beta^n$ 方法解，得到两个解后相加 $\Rightarrow a_{n}^{(p_{1})}+a_{n}^{(p_{2})}$
$f(n)=p(n)\beta^n$ 且 $p (n)$ 为 r 次方的多项式，且 $\beta$ 为常数
若 $\beta$ 不是characteristc equation的根，那么 $a_{n}^{(p)}=q(n)\beta^n$ 且 q 是至多为 r 次方的多项式
若 $\beta$ 是characteristc equation的根，且根 $\beta$ 的重复度为 t ，
那么 $a_{n}^{(p)}=q(n)n^t\beta^n$