算法基本概念
算法 Algorithm
-
对解决方案的完整而准确的描述，是指令的有限序列，每条指令表示一个或多个操作
算法的五大重要特性
有穷性
-
算法需在执行有穷步后结束，且每步在有穷时间内完成
确定性
-
算法的每条指令需有确切含义，对于相同的输入只能得到一个相同的输出
可行性
-
算法中的操作均可通过已实现的基本运算执行有限次实现
输入
-
有 0 或多个，取于特定对象集合
输出
-
有 1 或多个，与输出有特定关系
“好” 的算法标准
正确性
-
算法应能正确解决问题
可读性
-
算法应具良好的可读性
健壮性
-
对非法数据做出适当反应、处理
效率和低存储量需求
-
算法执行时间与执行过程中所需的最大存储空间
算法效率度量
时间复杂度（P6）
-
分类：最坏时间复杂度 平均时间复杂度 最好时间复杂度
- 平均时间复杂度：所有可能输入实例在等概率出现的情况下，算法的期望运行时间
频度
-
def 语句在算法中被重复执行的次数
T(n)
-
def 算法中所有语句的频度之和
渐进时间复杂度公式
两个计算规则
空间复杂度
S(n)
-
def 算法耗费的存储空间，是为实现计算所需信息的辅助空间
- 原地工作：算法所需的辅助空间为常量 O (1)