第一课
1.算法概念
1.有穷性(不能为死循环)
2.确切性(不能有歧义)
3.输入性(0或无数个)
4.输出性(1个以上)
5.可行性
2.复杂度分析
一.时间复杂度
一个算法的语句执行的次数称为语句频度或者时间频度,表示为T(n),也就是算法需要执行的运算次数,其中n表示问题的规模;
时间复杂度被我们称为记为O(n)
例如:
T(3);O(1)
aaaa...*a=ax=n
x=log a n;
(1).常见的时间复杂度
O(1),O(logn),O(n),O(nlogn),O(n!)
运算量 最大规模 速度扩大两倍后 n! 11 11 2n 26 27 n3 464 584 n2 10000 14142 nlog2n 4.5*106 8.6*106 n 100000000 200000000
如果N最大是108,那算法复杂度最多O(N);
如果N最大是104,那算法复杂度最大O(N2)
二.空间复杂度
算法所使用的额外的空间大小
时间复杂度-->TLE
空间复杂度-->MLE
三.模拟算法
1.审题立意
不遗漏地把题目中的所有条件都提取出来并分析题目样例
2.分析关系
分析给出的各个条件直接的关系,最好用流程图或简单列表列出
3.编写程序
用相应的语言,逐步求精的方法描述具体的算法
4.调试运行
调试代码并测试样例,如输出中间重要过程,观察中间过程是否正确
5.构造数据
构造一些更复杂,更全面的测试数据来检查程序的正确性
对拍