算法:解决特定问题的方法
特性:
有穷性
确定性
可行性
输入输出
好算法的标准:
正确性
易读性
健壮性
高效性
低存储性
时间复杂度:
常数阶
多项式阶
指数阶
对数阶
空间复杂度 算法占用的空间大小
空间复杂度的本身是指算法在运行过程中占用了多少存储空间,包括:
1 输入输出数据
2算法本身
3申请的额外空间
算法中有两条线索
一个是数据结构:数,矩阵,集合,串。排列,图
表达式,分布等
一个是算法策略:贪心,分治,动态规划,线性规划
搜索
上面讲到的内容有:
1将程序的执行次数作为时间复杂度的衡量标准
2时间复杂度通常用渐近上界符号f(n)表示
3衡量算法好坏通常考察算法的最坏情况
4空间复杂度只计算辅助空间
5递归算法的空间复杂度要计算递归使用的栈空间
6设计算法时尽量避免爆炸级增量复杂度