/**
* NO.01
* date：19.03.05
*/
在说时间复杂度之前，先来聊聊递归的内容。
递归
形成递归的几个要素
- Base case(基准情况)：结束递归的条件，当递归进行到某种程度时，结束递归。
- Making progress(不断推进)：递归之中的算法需要保证能让结果向着Base case前进。
一般是由归纳法证明。
3. Design rules(设计法则)：设计递归之中的运算，保证所有的递归法则都是能够运行的。
4. Compound interest rules(合成效益法则)：不能在递归之中做重复的事情（最重要的法则），不然效率会很低，例如斐波那契递归。
时间复杂度
Mathematical background
- 上界：T(N) = $ O $ (f(N)):
[小于等于]
- 上界：T(N) = $ O $ (f(N)):
If there are positive constants C and $N_0$ such that N$\geq n_0$ when T(N)$\leq$cf(N),如果有正的常数c和$n_0$，当N$\geq n_0$时使得T(N)$\leq$cf(N);
- 下届：T(N) = $\Omega$(g(N)):
If there are positive constants C and $N_0$ such that N$\leq n_0$ when T(N)$\leq$cg(N),如果有正的常数c和$n_0$，使得N$\geq n_0$时总有T(N)$\geq$cg(N);
- 相等：T(N) = $\Theta$(g(N)):
if and only if T(N) = $ O $ (f(N)) and T(N) = $\Omega$(g(N)),如果T(N) =$ O $ (g(N))成立时有T(N)= $\Omega$(g(N));
- 上界：T(N) = $ O $ (f(N))：
[小于]
if T(N) = $ O $ (p(N)) and T(N) $\neq$ $\Omega$(g(N))
规则：
当$T_1$(N) = $ O $ (f(N))的程序与$T_2$(N) = $ O $ (g(N))的程序合并在一起运行时
- 并列运行：$T_1$(N) + $T_2$(N) = max [$ O $ (f(N)),$ O $ (g(N))]; - 嵌套运行：$T_1$(N) * $T_2$(N) = $ O $ (f(N)) * $ O $ (g(N))；- 当T(N)是一个K次多项式时，那么$T_1$(N) = $\Theta$($N^k$);
- N·$\log k$ = $ O $(N) 是非常缓慢的；
4.典型增长类型：
| 数量级 | 能承受的大致规模 | 常见算法 |
|---|---|---|
| $O$(1) | 任意 | 直接输出结果 |
| $O$($\log n$) | 任意 | 二分查找、快速幂 |
| $O$(n) | 以百万计（五六百万） | 贪心算法、扫描和遍历 |
| $O$(n$\log n$) | 以十万计（三四十万 | 带有分治思想的算法，如二分法 |
| $O$($n^2$) | 以千计数（两千） | 枚举、动态规划 |
| $O$($n^3$) | 不到两百 | 动态规划 |
| $O$($2^n$) | 24 | 搜索 |
| $O$(n!) | 10 | 产生全排列 |
| $O$($n^n$) | 8 | 暴力法破解密码 |
注：
- 在$O$(N),忽略常数和低阶数；
- 可以通过(洛必达)求二者极限的方法（$ \lim_{N\rightarrow+\infty} \frac{f(N)}{g(N)} $）去求两种算法的相对增长率；
时间复杂度的计算
时间复杂度的特点
- 没有一个规定的时间单位。
- 一般都忽略常数和低阶数。
- （我忘了）
具体计算原则：
- 变量函数的声明不占用时间（可以忽略）
- 赋值、返回值，占一个时间单位。
- for循环中（以一般的常见循环
for(int i = 0;i <= n;i++)为例），赋值占一个时间单位，判断占N+1个时间单位，自加占一个时间单位。
几种常见的类型的时间复杂度
- T(N)=$O$(n$\log n$)
x = 2;
while(x < n/2 )
{
x = 2 * x;
}