day6贪心及算法评价-杨志军

《day6贪心及算法评价-杨志军》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、贪心及算法评价江苏省华罗庚中学杨志军2014年7月赣榆高级中学什么是算法【引例】求S=20+21+22+……+2n解法1：用循环求2i，再累加求和s:=0;fori:=0tondobegint:=1;forj:=1toidot:=t*2;s:=s+t;end;什么是算法【引例】求S=20+21+22+……+2n解法2：利用2i=2i-1*2，再累加求和s:=0;s:=1;t:=1;t:=1;fori:=0tondofori:=1tondobeginbegint:=t*2;t:=t*2;s:=s+t;

2、s:=s+t;end;end;什么是算法【引例】求S=20+21+22+……+2n解法3：利用公式2n+1-1s:=1;fori:=1ton+1dos:=s*2;s:=s-1;什么是算法用计算机编程解决实际问题的过程：分析设计编写运行程序问题开始问题算法程序验证结果解决程序=算法+数据结构施工流程图建筑设计图什么是算法算法，就是解决问题的方法和步骤。算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。算法的特

3、征可行性：算法中的每一个操作都应该是计算机可以执行的。确定性：算法中的每一步必须有确切的含义，不能有二义性。有穷性：一个算法必须在执行有限次运算或操作后结束。输入：算法执行前一般会有若干个输入，但有时也可以没有输入。输出：算法执行完毕，至少要有一个输出。算法的描述自然语言自然语言就是人们日常使用的语言，用自然语言描述算法虽然比较自然和容易接受，但叙述繁琐和冗长，易出现“二义性”。流程图流程图是用一组几何图形表示计算机中各种类型的操作，在图形上用扼要的文字和符号表示具体的操作，并用带

4、有箭头的流程线表示操作的先后次序。算法的描述N－S图输入a，b在流程图中完全去掉流程线，a>b全部算法写在一个矩形阵内，真假在框内还可以包含其他框的max←amax←b流程图形式。即由一些基本输出max的框组成一个大的框。Begin（算法开始）伪代码输入a，b伪代码是一种非正式的，类IFa>b则a→Max否则b→Max似于英语结构的，用于描述PrintMax模块结构图的语言。End（算法结束）程序算法的评价1、正确性算法的正确性是评价一个算法优劣的最重要的标准。2、可读性算法的可读性是指一

5、个算法可供人们阅读的容易程度。3、健壮性健壮性是指一个算法对不合理数据输入的反应能力和处理能力，也称为容错性。算法的评价4、时间复杂度算法的时间复杂度是指执行算法所需要的计算工作量。5、空间复杂度算法的空间复杂度是指算法需要消耗的内存空间。同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。算法的评价时间复杂度一般情况下，算法的基本操作重复执行的次数是模块n的某一个函数f(n)，因此，算

6、法的时间复杂度记做：T(n)=O(f(n))。在计算时间复杂度的时候，先找出算法的基本操作（原操作），然后根据相应的各语句确定它的执行次数，再找出T(n)的同数量级。算法的评价时间复杂度（1）x:=x+1O（1）（2）fori:=1tondoO（n）x:=x+1;（3）fori:=1tondoO（n2）forj:=1tondox:=x+1;算法的评价由于算法的时间复杂度考虑的是对于问题规模n的增长率，在实际计算的时候，一般只需求出它关于n的增长率或阶乘即可，不需要考虑常数项、低阶项和系数。例如：fo

7、ri:=1tondoO（n2）forj:=1toidox:=x+1;语句x:=x+1的执行次数为：(1+n)*n/2＝n2/2+n/2算法的评价常见的算法时间复杂度有：O(1)，O(n)，O(log2n)，O(nlog2n)，O(n2)，O(n3)，O(2n)等。当n很大的时候O(1)

8、则输出-1。方法一：逐个查找i:=1;while(i<=n)and(a[i]<>x)do最少时间：1i:=i+1;最多时间：nifi>n平均时间：n/2thenwriteln(-1)时间复杂度：O(n)elsewriteln(i);时间复杂度的举例【例1】给你n个整数，这些数已经从小到大排序了，查找其中有没有值为x的数，有则输出该数第一次出现的位置,没有则输出-1。方法二：二分查找最少时间：1i:=1;j:=n;mid:=(i+j)div2;最多时间：log2nwhi