算法第一课 - 认识
2021-05-26 本文已影响0人
jeneen1129
算法
定义：
解题方案的准确而完整的描述，是一系列解决问题的清晰指令。
五个特征
- 有穷性
有限步骤 - 确定性
每个步骤没有二意 - 输入 >= 0(may have inputs)
输入有0或者多个 - 输出 >= 1(more than one output)
必定有一个或者多个输出，代表解决方案的结果 - 可行性（effectiveness)
每个步骤都是可执行的
评价
- 稳定性
比如排序算法中
- 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
- 不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
- 时间复杂度
执行算法所要花费的时间，通常直接使用函数 o(f(n)) 来表示。 - 空间复杂度
算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。 - 可读性： 易于理解
- 鲁棒性、健壮性
对不合理数据的反应和处理能力，也叫容错性
方法
- 递推法
- 递归法
- 穷举法
- 贪心算法
- 分治法
- 动态规划法
- 迭代法
- 分支界限法
- 回溯法
