算法重要特性
确定性: 算法中每一种运算都是确定的，有明确的定义，运算执行是清楚得无二义。
能行性: 每一种运算能由人用纸和笔在有限的时间内完成。
输入：算法有0或多个输入，算法开始前提前给出
输出：算法又一个或多个输出，同输入又某种特定的关系
有穷性： 总是在执行有穷步得运算后终止
凡是算法必须满足以上5中特性
算法的主要内容
- 如何设计算法
- 如何表示算法 (Spark等算法描述语言)
- 如何确认算法 (合法得输入可以得到正确得结果)
- 如何分析算法 (计算时间和存储空间定量分析)
- 如何测试程序 (调试和作时空分布图，调试只能指出错误，但不能证明他们不存在错误；做时空分布图用各种数据执行调试来确认算法得正确性，准确的计算出结果所需要花费得时间和空间。)
分析算法
算法的时间复杂度：
- 复杂度计算时，基本运算定义为加减乘除，均为固定常数时间
- 多项式复杂度 1 < log(n) < n < nlog(n) < n^2 < n^3
- 指数级复杂度 2^n < n! < n^n
- 当数量级增大时指数级复杂度增长迅速，所以应尽可能降低为多项式复杂度以节省运算时间。
| logn | n | nlogn | n^2 | n^3 | 2^n |
|---|---|---|---|---|---|
| 0 | 1 | 0 | 1 | 1 | 2 |
| 1 | 2 | 2 | 4 | 8 | 4 |
| 2 | 4 | 8 | 16 | 64 | 16 |
| 4 | 16 | 64 | 256 | 4096 | 65536 |
| 5 | 32 | 160 | 1024 | 32768 | 4294967296 |
- 算法时间表示：
上界(最坏)、下界(最好)、平均
几个计算复杂度得例子：
