定义时间复杂度¶

分析的是渐进的增长速率

Big Oh¶

Basic idea $f(n)\in O(g(n))$
- For Sufficiently large input size, $g(n)$ is an upper bound for $f(n)$

0 一些有意思的公式可以使用¶

斯特林公式(Stirling' s formula)¶

\[ n!\approx \sqrt{ 2\pi n }\left( \frac{n}{e} \right)^n \]

1.通过递归表达式求解。¶

这类问题本质是数列求和问题。通常会用到 数学归纳法 常见数列求和 等知识点。

替换法 -数学归纳法¶

大胆假设，小心求证。 核心原理：先猜测出一个时间复杂度，然后根据递归表达式证明随着 n 的增大，不会逾越这个时间复杂度。

这里介绍一个有用的放缩方法。

Theorom 1 积分求和放缩¶

Given $f(x)$是一个增函数则 $$ \int_{0}^nf(x)dx\leq\sum {i=1}^{n}f(i)\leq \int{1}^{n+1}f(x)dx $$ 画图，将求和看成一个个宽度为1的小矩形，将定积分看成函数与x轴围成的面积，即可得到。常利用与求和放缩证明。特别是涉及到$logn$这类不容易求和的函数。

2.重新思考乘方的复杂度¶

[!Example] Calculate $S_n$,where $S_{n}$ is $\sum_{i=0}^{n}f_{n}$, and$f_{n}$is the $n$-th Fibonacci number. Base: $f_{0}=0,f_{1}=1,f_{2}=1$... Design an algorithm in $O(\log n)$ time to do it. Hint: One multiplication (addtion) takes O(1) time. And $f(n)$ satisfies $$ f_{n}=\frac{1}{\sqrt{ 5 }}{\left[ \left( 1+\frac{\sqrt{ 5 }}{2} \right)^n-\left( {1-\frac{\sqrt{ 5 }}{2}} \right)^n\right]} $$

$Solution$: easily to find that $f_{n}=f_{n-2}+f_{n-3}+\cdots+f_{2}+f_{2}+f_{1}$ So, $$ S_{n}=2f_{n}+f_{n-1}-1 $$ The key is to give an algorithm to calculate $x^n$ in $\Theta(\log n)$ time $x^n=x^{n/2}\times x^{n/2}$ $T(n)=T\left( \frac{n}{2} \right)+1$ So $T(n)\in \Theta(\log n)$

You are given a collection of n bolts of different widths and n corresponding nuts. You are allowed to try a nut and bolt together, from which you can determine whether the nut is larger or smaller than the bolt, or matches the bolt exactly. However, there is no way to compare two nuts together or two bolts together. The problem is to match each bolt to its nut. Design an algorithm for this problem with average case efficiency in $\Omega(n\log n)$

Solution:

[!Example|Second] Solve the recurrence and analyze asymptotic upper and lower bounds for $a_{n}$, i.e., find $f(n)$ with $a_n\in \Theta(f(n)):$ $$ (n-1)a_{n}=na_{n-1}+n^2+n\;for \;n>1\; with\; a_{1}=1 $$

3. 递归复杂度：主定理¶

也可以用递归树来观察

Divide-and-conquer: $T(n)=bT\left( \dfrac{n}{c} \right)+f(n)$ 主定理： Define $E=\frac{{\log b}}{\log c}$

$f(n)\in O(n^{E-\varepsilon})$, then $T(n)\in\Theta(n^{E})$
$f(n)\in\Theta(n^{E})$, then $T(n)\in\Theta(f(n)\log n)$
$f(n)\in \Omega(n^{E+\varepsilon})$, and $f(n)\in O(n^{E+\delta}),\delta\geq \varepsilon$ then $T(n)\in \Theta(f(n))$

Smooth Functions¶

$$ f(2n)\in \Theta(f(n)) $$ Then we said $f(n)$ is a smooth function

Let $f(n)$ be a smooth function Then, for any fixed integer $b\geq 2$， $$ f(bn)\in \Theta(f(n)) $$

特殊题：多个递归式¶

可以考虑画出递归树，考虑深度最大的——影响最大的。具体可以考虑这道题： 2.16 13. $$ T(n)=T\left( \frac{n}{2} \right)+T\left( \frac{n}{4} \right)+T\left( \frac{n}{8} \right)+n $$

Method 1: 先猜后证+替换法¶

先猜后证：$T(n)=\Theta(n)$，利用替换法证明。要证：$T(n)=\Theta(n)$，即 $n\to +\infty,T(n)=cn$ 由归纳假设 $$ \begin{align} T(k) & =T\left( \frac{k}{2} \right)+T\left( \frac{k}{4} \right)+T\left( \frac{k}{8} \right)+k \ & =k\cdot\left( \frac{c}{2}+\frac{c}{4}+\frac{c}{8}+1 \right)=\left( \frac{7}{8}c+1 \right)\cdot k \ & =c\cdot k \end{align} $$ 取 $c=8$（解了个方程），上述结论成立，得证。

Method 2：递归树求和¶

首先该结构显然不符合 Master 定理使用条件，我们想到直接使用递归树逐层求和。

这里有一个重要的 insight：由于后面跟了多个不同高度的递归式，在趋于无限情况下，我们只需要考虑挂的最庞大的，也就是最左侧的树，它高度最高，它会 domain the complexity

最左侧的树什么时候时候结束呢？最多高度为 $\log n$

![[recursive-tree-p13.png]] $$ \sum_{k=1}^{\log n}{\left( \frac{7}{8} \right)}^{k}n $$ 在 n 趋近于无穷的时候，容易证明 $\in\Theta(n)$