算法第一课 - 认识

算法

定义：
解题方案的准确而完整的描述，是一系列解决问题的清晰指令。

五个特征

1. 有穷性
   有限步骤
2. 确定性
   每个步骤没有二意
3. 输入 >= 0(may have inputs)
   输入有0或者多个
4. 输出 >= 1(more than one output)
   必定有一个或者多个输出，代表解决方案的结果
5. 可行性（effectiveness)
   每个步骤都是可执行的

评价

1. 稳定性
   比如排序算法中

• 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
• 不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。

2. 时间复杂度
   执行算法所要花费的时间，通常直接使用函数 o(f(n)) 来表示。
3. 空间复杂度
   算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。
4. 可读性： 易于理解
5. 鲁棒性、健壮性
   对不合理数据的反应和处理能力，也叫容错性

方法

1. 递推法
2. 递归法
3. 穷举法
4. 贪心算法
5. 分治法
6. 动态规划法
7. 迭代法
8. 分支界限法
9. 回溯法