1.2算法分析与设计 3、算法的正确性:只有保证正确的解算结果,才能讨 论算法的好坏。如:设计一个求三角形面积的算法,给定 三角形的三条边分别为a,b,C,求面积area的简单算法为: stepl read(a, b, c) step2 S:(a+b+c)/2 step3 area=sqrt(s*(s-a)*(s-b)*(S-c) step4 write(area) 显然、该题上机运行后有时正确、有时错误,甚至死 机。为什么?应从以下几个方面考虑: ①数学原理正确吗?三角形的两边之和应大于第三边? ②解题条件正确吗?边常能为负数?,能否开平方? ③执行路径合理吗?程序(调函数)中常有判断转移,对?
16 1.2 算法分析与设计 3、算法的正确性：只有保证正确的解算结果，才能讨 论算法的好坏。如：设计一个求三角形面积的算法，给定 三角形的三条边分别为a，b，c，求面积area的简单算法为： step1 read(a,b,c) step2 S:=(a+b+c)/2 step3 area=sqrt(s*(s-a)*(s-b)*(s-c)) step4 write(area) 应从以下几个方面考虑： ① 数学原理正确吗？三角形的两边之和应大于第三边? ② 解题条件正确吗？边常能为负数？，能否开平方？ ③ 执行路径合理吗？程序(调函数)中常有判断转移，对？ 显然、该题上机运行后有时正确、有时错误，甚至死 机。为什么？ a b c
1.2算法分析与设计 3、算法的正确性:“正确”的含义在通常的用法 中有很大的差别(不严密),大体可分为以下四个层 次④程序可运行:程序不含语法错误;可用于运行 ②结果也正确:对几组输入数据能得出满足要求的结果 ③条件下正确:程序对一切合法的输入数据都能产生满 足规格说明要求的结果。符合程序功能的基本要求。 ④完全正确:对于精心选择的典型、苛刻而带有刁难性 的数据能够得出满足规格说明要求的结果;由测试完成。 最简单和最直接的算法往往不是最有效的,但算法的简 单使得证明其正确比较容易,同时便于编写、修改、阅读 和调试,所以应强调简洁。但对经常使用的算法来说,高 效率(减少运行时间和压缩存储空间)比简单性更为重要
17 1.2 算法分析与设计 3、算法的正确性：“正确”的含义在通常的用法 中有很大的差别(不严密)，大体可分为以下四个层 次：① 程序可运行：程序不含语法错误；可用于运行。 ② 结果也正确：对几组输入数据能得出满足要求的结果 ③ 条件下正确：程序对一切合法的输入数据都能产生满 足规格说明要求的结果。符合程序功能的基本要求。 ④ 完全正确：对于精心选择的典型、苛刻而带有刁难性 的数据能够得出满足规格说明要求的结果；由测试完成。 最简单和最直接的算法往往不是最有效的，但算法的简 单使得证明其正确比较容易，同时便于编写、修改、阅读 和调试，所以应强调简洁。但对经常使用的算法来说，高 效率(减少运行时间和压缩存储空间)比简单性更为重要
1.2算法分析与设计 4、时间复杂性分析:何达到高效?省时省内存 学习时间复杂度意义:时间复杂性能给出算题运算需要 的估计时间、相应计算机的解题时间及如何选择计算机 ①时间频度:一个算法中的语句执行次数称为语句频度 或时间频度。其实质是在一个循环中找关键操作 执行一个算法所耗费的时间,理论上难以计算,须上机 运行测试。但实际不能也不必,只需知道各算法的花费时 间。同时一个算法花费的时间与算法中语句的执行次数成 正比例。记为T(n)。如下列算法段的语句频度: 分析:该算法为一个二重循环,执行次 for(=1i;i=n1计+)数为内外循环次数相乘,但内循环次数 forG=1; j<=1; j++) 不固定,与外循环有关,因些,时间频 X=X+1 度T(n)=1+2+3+.+n=mn+
18 4、时间复杂性分析：何达到高效? 省时省内存。 学习时间复杂度意义：时间复杂性能给出算题运算需要 的估计时间、相应计算机的解题时间及如何选择计算机。 ① 时间频度：一个算法中的语句执行次数称为语句频度 或时间频度。其实质是在一个循环中找关键操作。 执行一个算法所耗费的时间，理论上难以计算，须上机 运行测试。但实际不能也不必，只需知道各算法的花费时 间。同时一个算法花费的时间与算法中语句的执行次数成 正比例。记为T(n)。如下列算法段的语句频度： 1.2 算法分析与设计 for(i=1; i<=n; i++) for(j =1; j <=i ; j++) x=x+1; 分析：该算法为一个二重循环，执行次 数为内外循环次数相乘，但内循环次数 不固定，与外循环有关，因些，时间频 度T(n)=1+2+3+…+n= 2 n(n+1)
1.2算法分析与设计 4、时间复杂性分析: ②算法的时间复杂度:算法中实现基本操作的语句(基 本语句)重复执行的次数f(m),称为算法的频度。 记作:T(n)=O(r(m)随问题规模n的增大,算法的频 度T(m)和重复次数f(n)的增长率同阶。 例1:x+=5;单个语句频度为1,则程序段的时间复 杂度为T(n)=O(1)。 12: for(i=1; K<=n;++i) /kn+1* for gj=1: j<=n; ++i) /n(n+1)*/ c[= * n 共执行:T(n)=2m2+2n+1当n充分大时T(n)与n2是同 阶的。该算法时间复杂度为:T(m)=O(n
19 4、时间复杂性分析： ② 算法的时间复杂度：算法中实现基本操作的语句(基 本语句)重复执行的次数f(n) ，称为算法的频度。 记作：T(n)=O(f(n)) 随问题规模n的增大，算法的频 度T(n)和重复次数f(n)的增长率同阶。 例1： x+=5; 单个语句频度为1，则 程序段的时间复 杂度为T(n)=O(1)。 1.2 算法分析与设计 例2: for (i=1; i<=n; ++i) /* n+1 */ for (j=1; j<=n; ++j) /* n(n+1) */ c [i][j]=0; /* n2 */ 共执行：T(n)=2n2+2n+1 当n充分大时 T(n)与n 2是同 阶的。该算法时间复杂度为：T(n)=O(n2 )
1.2算法分析与设计 4、时间复杂性分析:②时间复杂度 1).O(n2)复杂度:在时间频度中,n称为问题的规模, 当n不断变化时,时间频度T(n)也会不断变化。要知道变 化规律,引入时间复杂度概念 设T(n)的一个辅助函数为g(n),定义为当n大于等于某 足够大的正整数n时,存在两个正的常数A和B(其中 A≤B),使得AT(n)g(n)<B均成立,则称g(n)是T(n)的同 数量级函数。把T(n)表示成数量级的形式为: T(n)=O(g(n),其中大写O为 Order(次阶序量级)的首字母。 例如,若T(m)=n(n+1)2,则有1/4≤T(n)/m2<12,故它 的时间复杂度为0(m2),即T(m)与m2数量级相同
20 4、时间复杂性分析： ② 时间复杂度 1). O(n2 )复杂度： 在时间频度中，n称为问题的规模， 当n不断变化时，时间频度T(n)也会不断变化。要知道变 化规律，引入时间复杂度概念。 1.2 算法分析与设计 例如，若T(n)=n(n+1)/2，则有 1/4≤T(n)/n2≤1/2，故它 的时间复杂度为Ｏ(n 2 )，即Ｔ(n)与n 2 数量级相同。 设T(n)的一个辅助函数为g(n)，定义为当n大于等于某 一足够大的正整数n0时，存在两个正的常数A和B（其中 A≤B），使得A≤T(n)/g(n)≤B均成立，则称g(n)是T(n)的同 数量级函数。把 T(n)表示成数量级的形式为： T(n)=Ｏ(g(n)), 其中大写Ｏ为Order(次/阶/序/量/级)的首字母