！！复习算法考试所用，代码为老师课堂手写，逻辑没错，应该有点小问题，需要修改才能运行，仅供思路参考
1.1 算法：解决问题的办法，是由若干条指令组成的有穷序列。
满足:
- 输入(I)：有零个或多个输入
- 输出(o): 至少一个输入
- 确定性：组成算法的每条指令，必须是明白无误的无歧义。
- 有限性：算法每条指令执行次数是有限的，时间有限。
程序：算法的计算机语言实现，可以无限循环。
算法的描述：
- 自然语言
- 类计算机语言，如类c
- 计算机语言，如c++,c,java
- 混合
1.2 算法复杂度
例子：设算法输入规模为n,同时求最大最小
两两比较 =》 大的放偶序，小的放奇序=》最大值肯定在偶数组，最小值肯定在奇数组
比较次数 n/2+n/2-1+n/2-1
设算法的输入规模为 n
C(A,I,n) 包括 T(A,I,n) 时间 ，S(A,I,n) 空间
即算法复杂度包括时间复杂度和空间复杂度
设某计算机运行算法的某个实例I
| 原运算 | O1 | O2 | ...On |
|---|---|---|---|
| 用时 | t1 | t2 | ...tn |
| 次数 | e1 | e2 | ...ek |
则T(A,I,n) = 累加ei * ti（太菜了，累加符号打不出来）
- 最坏 Tmax(A,n) = max T(A,I,n) I 属于 Dn Dn : 输入规模为n的全体空间
- 最好 Tmin(A,n) = min T(A,I,n) I 属于 Dn Dn : 输入规模为n的全体空间
- 平均 Tave(A,n) = 累加 T(A,I,n) * P(I) I 属于 Dn
注意：实际中：对时间的考察：对某个主要次数的考察，且单独处理
对矩阵乘积 Ann* Bnn=》
- 加法运算 A (n) = (n-1)* n^2 = n^3 - n^2
- 乘法运算 P(n) = n*n^2
- Aave(n) = Amin(n) = Amax(n) =n^3 - n^2 //等概率平均
- Pmin(n) = Pmax(n) = n^3
例如 线性查找元素
template<class T>
int find(T* a,int n,const T & x)
{
for(int i = 0;i<n;i++)
{
return ;
}
return -1;
}
主要运算： 比较"==",规模 n
1.最好情况： Tmin(n) = 1;
2.最坏情况： Tmax(n) = n;
3.平均 : Tave(n) = (n+1)/2 <=若等概率
算法是程序设计的灵魂
1.2 复杂度的度量
一个算法A，输入量为n
复杂度（cn）=》（时间，空间）{最好，最坏，平均}是非递减函数
若 C 为函数 f(n)，采用渐进分析方法
记号 ： O,W,θ,o,w
1. O(fn) f(n)为g(n)上界 g(n) = O(f(n)) 含义 ： g(n)的复杂度不超过f(n) 例如 1/2 * n^2 = O(n^2)
2. W(fn) f(n)为g(n)下界 g(n) = W(f(n)) 含义 ： g(n)的复杂度超过f(n) 例如 2 * n^2 = W(n^2)
3. θ(fn) g(n) = θf(n）含义：g(n)与f(n)同级别
4. o(fn) f(n)为g(n)严格上界 例如 1000n = o(n^2)
5. w(fn) f(n)为g(n)严格下界
定理
- g(n) = O(f(n))<=>f(n) =W(g(n))
- g(n) = θ(f(n))<=>f(n) = θ(f(n))
- g(n) = o(f(n))<=>f(n) =w(g(n))
多项式函数复杂度
- 设P(n**) = ak* n^k + a（k-1）* n^（k-1）+...a1* n + a0
- 则P(n) = θ(n^k)
- 当然 P(n) = O(n^k)
- 1n^2-10n+9 = θ(n^2) = O(n^2)
常用的复杂度函数
- logn,nx(0<x<1),n,n*logn,n(1+x),n2,n3....... =>多项式级别
- 2^n,n! =>指数级别
算法的共识：
- 容易解决的问题，即多项式级别
- 难的问题，即指数级别
定理：O(f(n)+g(n)) = O(max(f(n),g(n)))