算法概念
复杂度
- 时间复杂度
- 定义
- 常数时间的操作
- 执行时间固定的操作都是常数时间的操作
- 算术运算
- 位运算
- 赋值、比较、自增、自减
- 数组寻址操作
- 以选择排序为例
- 只需要关注最高阶的数值
- 常数时间的操作
遍历0 - N个数, 交换一次
遍历1 - N-1个数, 交换一次
遍历2 - N-2个数, 交换一次
…
遍历结束
结论：所有遍历的次数为 $an^2+bn+c$ ,交换次数为
n,时间复杂度为 $n^2$
- 空间复杂度
算法评估标准
- 时间复杂度
- 通过最差条件算出时间复杂度
- 额外空间复杂度
算法实现
选择排序
冒泡排序
插入排序
二分法
- 寻找某个数是否存在某个正序数组中
- 在一个正数组中找到大于等于某个数的最左侧位置
- 局部最小值问题
- 返回一个无序数组局部最小值问题
Tips
- 算法的过程与语言无关
- 分析一个算法流程复杂度的前提是对流程很清晰
