一、常见阶大小比较

从大到小：

• 超指数阶：$n^n$，$n!$
• 指数阶：$9^{n/2}$, $2^n$
• 多项式阶：$n^3$, $n*log(n)$, $n^{1/2}$
• 对数阶：$log^2(n)$, $log(n)$, $log(log(n))$
• 常数阶：100, 1
  下题需要保留阶最高的部分：

二、算法复杂性估计函数

$$ \lim_{n \to \infty} \frac{f(n)}{g(n)} = \begin{cases} (大于0的常数或)0 &&& f(n)=O(g(n))上界&-----f(n)\le cg(n)\\ (大于0的常数或)无穷 &&& f(n)= \Omega(g(n))下界&-----f(n)\ge cg(n)\\ 大于0的常数 &&& f(n)= \Theta(g(n))确切界&-----f(n)=cg(n)\\ 0 &&&f(n)=o(g(n))上界&-----f(n)< cg(n) \end{cases} $$

可以发现都是针对f(n)在讨论，很容易得出下题答案：

三、几个常用替换的式子

1.Stirling公式：

$$n! \approx {(2 \pi n)}^{1/2}{(n/e)}^n$$

2.阶乘和二项式系数

$$C_n^k = C_n^{n-k} \\ C_n^n = C_n^0 = 1 \\C_n^k = C_{n-1}^k +C_{n-1}^{k-1} $$

帕斯卡三角形可以辅助记二项式系数：

$$\sum_{j=0}^{n}{C_{n}^j}x^j= {(1+x)}^n $$

3.和式

$$\sum_{j=1}^{n}{a_{n-j}} = \sum_{j=0}^{n-1}{a_j} \\ \sum_{j=0}^n{j \over 2^j} = \sum_{j=1}^n{j \over 2^j} = 2-{{(n+2)} \over {n^2}} = \Theta(1) \\ \sum_{j=0}^njc^j = \sum_{j=1}^njc^j = \Theta(nc^n)$$

4.定积分与和式转换

$$\int_m^{n+1} f(x) dx \le \sum_{j=m}^nf(j) \le \int_{m-1}^nf(x)dx 递减函数 \\ \int_{m-1}^{n} f(x) dx \le \sum_{j=m}^nf(j) \le \int_{m}^{n+1}f(x)dx 递增函数$$

可以采用画图的方法辅助记忆它的上下界：
以一个递增的函数为例，我们要求1（m）~6（n）他的面积，每一个小矩形$1*f(j)$如果我们积分每个点左边的矩形，那么总面积就是偏小的，积分右边矩形就会稍微偏大，这就找到了上下界，当函数平行于X轴时就会有等号。递减也是一个道理。
但是，如果是logn等函数会遇到定义域不存在的情况。我们应该从和式中把（在积分中）没有定义的点先拿出来，再去积分。

用代数方法证明就是放大缩小去求，用积分方法证明就是用上面那个公式。可以看到积分方法求时等式左边按公式应该为$\int_0^n jlogj !\ dj$定义域
不存在，所以对于右边：

$$\sum_{j=1}^njlogj=\sum_{j=2}^njlogj+1log1=\int_{2-1}^njlogj \!\ dj+1log1$$

四、计算次数

算法:COUNT
输入:n=2k,k为正整数。
输出: count的值 。
count=0
while n>=1
	for j=1 to n
		count=count+1
	n=n/2
return count
end COUNT

while要执行k+1次，$k=log_2n$.for循环在每次while的基础上执行n次所以(k+1)n即$nlog_2n$次计算

算法: MERGE
输入:数组A[1..m]和它的三个索引p, q, r, 1<=p<=q<r<=m。
两个子数组A[p..q]和A[q+1..r]各自按升序排列。
输出:合并两个子数组A[p..q]和A[q+1..r]的升序数组A[p..r]
for(s=p, t=q+1, k=p; S<=q and t<=r; k++)
	if A[s]<=A[t] //两个指针从两个头开始排序
		B[k]=A[s]; //B[p..r]是个辅助数组
		S=S+1;
	else
		B[k]=A[t];
		t=t+1;
if s=q+1 
	B[k..r]=A[q+1..r] 
else
	B[k..r]=A[s..q]
A[p..r]=B[p..r]
end MERGE

两段相邻数组分别有序，两个指针将两段变为有序的。2(r-p+1)先遍历一次排序，在从排好序的辅助数组移回来。

void insertion_ sort(Type *a, int n){
								// 代价 次数
								// ti: for的第i次while的循环次数
for (int i=1; i<n; i++){		// c1   n(比较语句)
	key=a[i];					// c2   n-1
	int j=i-1;					// c3   n-1
	while( j>=0 && a[j]>key ){  // c4   sum ti
		a[j+1] = a[j];			// c5   sum of (ti-1)
		j--;					// c6	sum of (ti-1)
	}
	a[j+1]=key; 				// c7   n-1
}
}

插入排序的思想是左手为空，右手的牌按序插入。这里t是个不确定的数，但是还是可以得出计算次数为：

$$c_1n+c_2(n-1)+c_3(n-1)+c_4\sum_{i=1}^{n-1}{t_i}+c_5\sum_{i=1}^{n-1}{(t_i-1)}+c_6\sum_{i=1}^{n-1}{(t_i-1)}+c_7(n-1)$$

最好情况就是已经排好序了，c5与c6都是0，每次for的while都只跑一次。
$$c_1n+c_2(n-1)+c_3(n-1)+c_4(n-1)+c_7(n-1) = O(n)$$
最坏情况就是倒序排的，n张牌每次都比上一次多查找一个。

$$\sum_{i=1}^{n-1}{(t_i-1)} = n(n-1)/2$$

复杂度$O(n^2)$

1. COUNT4
2.count <-- 0
3.for i ←- 1 to Llogn」
4.	for j ←- i to i+5
5.		for k ←- 1 to i^2
6.         count ←- count +1
7.		end for
8.  end for
9.end for
(a)第6步执行了多少次?
(b)要表示算法的时间复杂性，用0和O哪个符号更合适?为什么?
(c)算法的时间复杂性是什么?

a）思路是把每次for循环乘起来。
$$\sum_{i=1}^{\lfloor logn \rfloor}\sum_{j=i}^{i+5}\sum_{k=1}^{i^2}{1}$$内层指的是从1到$i^2$个1相加$=\sum_{i=1}^{\lfloor logn \rfloor}\sum_{j=i}^{i+5}{i^2} = 6\sum_{i=1}^{\lfloor logn \rfloor}{i^2}$
利用平方和求和公式$n(n+1)(2n+1)/6$进一步化简$=\lfloor logn \rfloor(\lfloor logn \rfloor +1)(2\lfloor logn \rfloor+1)$
b） O 因为对于算出的确切的计算次数，这个用于表示算法时间复杂性的函数是它上界。
c）$O(log^3n)$

五、解递归方程式

1.线性齐次递推式（二阶）

对于递推式:$$f(n)=a_1f(n-1)+a_2f(n-2)+…+a_kf(n-k)$$我们想要得到$f(n)$的确切解，它的解往往是$x^n$于是我们可以把这个递推式的等价于:$$x_n=a_1x^{n-1}+a_2x^{n-2}+…+a_kx^{n-k}$$将两边同时除以$x^{n-k}$并且移项可以得到与n无关还能解出x的式子$$x^k-a_1x^{k-1}-a_2x^{k-2}-…-a_k = 0$$这个就是常说的特征方程。

步骤	例1	例2
序列	1,4,16,64,256	1,1,2,3,5,8(斐波拉契)
递推关系	f(n)=3f(n-1)+4f(n-2)	f(n)=f(n-1)+f(n-2)
特征方程	$x^2-3x-4=0$	$x^2-x-1=0$
特征根	$x_1=-1,x_2=4$	$x_1= { {1+\sqrt5} \over 2},x_2={ {1-\sqrt5} \over 2}$
通解	$f(n) = c_1{(-1)}^n+c_24^n$	$f(n)=c_1\left( { {1+\sqrt5} \over 2} \right)^n+c_2\left( { {1-\sqrt5} \over 2} \right)^n$
带入序列中的点	$c_1=0,c_2=1$	$c_1={1\over {\sqrt5}},c_2=-{1\over {\sqrt5}}$
最终解	$f(n)=4^n$	由于n无穷大$c_2\left( { {1-\sqrt5} \over 2} \right)^n$趋于0,$f(n)={1\over {\sqrt5}}\left( { {1+\sqrt5} \over 2} \right)^n$

还有种特殊情况：$x_1=x_2=x$时$f(n)=c_1nx^n+c_2x^n$

2.非齐次递推式

2.1 f(n)=f(n-1)+g(n)

对于这一类g(n)是一个已知的函数，推导可得：
$$f(n) = f(n-1)+g(n) = \big(f(n-2)+g(n-1)\big)+g(n) = f(0)+ \sum_{j=1}^ng(j)$$

这道题麻烦点在于怎么把前面的系数3搞没了。由1我们知道，这种递推式是$f(n)=x^n$变形令$f(n)=3^nq(n), f(0)=q(0)=3$于是乎原式变为：

$$3^nq(n)=3*3^{n-1}q(n-1)+2^n \\ q(n)=q(n-1)+{(2/3)}^n\\ q(n)=q(0)+\sum_{j=1}^n{{(2/3)}^n}\\ f(n)=3^n*\big(3+{(2/3)(1-{(2/3)}^n) \over {1-(2/3)}}\big) \\ f(n)=5*3^n+2^{n+1}$$

2.2 f(n)=f(n-1)*g(n)

对于这一类g(n)也是一个已知的函数，推导可得：
$$f(n) = f(n-1)*g(n) = \big(f(n-2)*g(n-1)\big)+g(n) = f(0)\prod_{i=1}^ng(i)$$

2.3 f(n)=f(n-1)*g(n)+h(n)

可以直接推，也可以带点技巧推。结果：$$=\prod_{i=1}^ng(i)\big( f(0)+\sum_{j=1}^n{h(j) \over{\prod_{i=1}^ng(i)} } \big)$$

2.4 f(n)=af(n/c)+g(n)

$$f(n)=\begin{cases} d& \text{n=1}\\af({n\over c})+bn^x& \text{n >= 2} \end{cases}$$

其中d非负常量，g(n)非负函数，a，c正数。设$n=c^k$

$$f(n)=\begin{cases} bn^x*log_cn^x+dn^x&{a=c^x}\\ \big(d+{{bc^x}\over{a-c^x}}\big)n^{log_ca}-\big({{bc^x}\over{a-c^x}}\big)n^x& {a\neq c^x} \end{cases}$$

这道题就没有为难菜鸡，直接把方向给了。这种做法在遇到f(n/2)的情况下叫做更换变元法
$$f(2^k)=f(2^{k-1})+2^k=f(2^0)+\sum_{i=1}^k2^i=2^{k+1}-1 =2n-1\
g(2^k)=2g(2^{k-1})+1=\sum_{i=0}^k2^i=2^{k+1}-1=2n-1$$
也可以直接套公式:
对于f $d=1,a=1,c=2,b=1$
对于g $a=2,c=2,b=1,d=1$
这些公式太惨绝人寰了，其他还有一些和2.4一样复杂的，等遇到了再补充上去。

六、p、np、np-hard、np-complete问题

p、np、np-hard、np-complete问题这篇文章讲的很清晰，附上一张从文章里拿的