第1章绪论13-14new.ppt

* 程序代码本身所占空间对不同算法通常不会有数量级之差别，因此在比较算法时可以不加考虑； 算法的输入数据量和问题规模有关，若输入数据所占空间只取决于问题本身，和算法无关，则在比较算法时也可以不加考虑； 由此只需要分析除输入和程序之外的辅助变量所占额外空间。 * 类似于算法的时间复杂度，通常以算法的空间复杂度作为算法所需存储空间的量度。定义算法空间复杂度为 * * * * * * Int divide(int a, int b ) { …… } * * * * * * * * 引： 算法 + 数据结构 = 程序设计 可见，一个程序运行效率的高低，不仅与数据结构 有关，而且与算法紧密联系，它是程序设计的另一个不 可缺的要素，因此在讨论数据结构的同时免不了要讨论 相应的算法。 当数据结构确定时，一个算法的好坏决定一个程序运 行的效率高低。 * （算法是程序设计的另一个不可缺的要素，因此在讨论数据结构的同时免不了要讨论相应的算法。） * * * 0个输入：如“求100以内的素数”，操作对象是自然数列，可以由变量逐个增1生成。 * 多问几个为什么？ * * * * * * * 采用事前分析估算法，如何估算算法的时间效率？先看与算法执行时间相关的因素有哪些？ * 1：好算法效率高、执行时间短 2：排序：10------10000 结束语：一个问题有多种解法，当问题规模一定时，通过衡量每一个算法的执行时间大小，就可以比较各个算法的好坏。 那么，如何衡量每一个算法的执行时间大小？ * 一个算法的执行时间与什么 有关?: 从上述诸影响因素中可知，当忽略后三项时，处理问题的某一算法确定，则其运行时间仅与问题规模有关。 * 衡量不同算法的优劣应该以其随问题规模的增长而“增长的趋势”为准则，即比较不同算法的执行时间随问题规模的增长而“增长的趋势”大小--大：效率低；小：效率高, 例如f(n)=an3 ;f(n)=bn2 “ O” 的数学含义是，若存在两个常量 C 和n0 ，当nn0 时，| T (n)|≤C|f(n)|, 则记作： T (n) = O(f(n)) 它表明算法的执行时间是和f(n)“同数量级”的。 “渐近”是相对其它时间复杂度(如计算程序步数)而言， 但由于在本课程中不讨论其它类型的时间复杂度，故以后 均简称时间复杂度。 * 一个算法的执行时间应该是算法中所有语句(操作)的执行时间之和! 算法 = 控制结构 + 原操作 任何一个算法都是由一个“控制结构”和若干“原操作”组成的，因此一个算法的执行时间可以看成是所有原操作的执行时间之和　　　∑( 原操作(i)的执行次数 X 原操作(i)的执行时间 ) “原操作“在这里是指高级程序设计语言中固有数据类型的操作，如两个整型数相加或交换，显然每个原操作的执行时间和算法无关，相对于问题的规模是常量。因此估算一个算法的执行时间，只需统计算法中所有原操作的执行次数即可。在一个算法中包含很多原操作，但其中一定存在一个对算法执行时间其主要作用的原操作，称这种原操作为”基本操作”，换句话说，算法的执行时间主要取决于”基本操作“的重复次数。由于算法的时间复杂度是算法执行时间增长率的量度（其随问题规模的增长而“增长的趋势” ），因此只需要考虑在算法中“起主要作用”的“基本操作”的重复次数即可，而其他原操作的重复次数相对基本操作来说或者是一个常量或者变化率很小，可以忽略。 “基本操作”的重复执行次数和算法的执行时间成正比。 * 在一个算法中包含很多原操作，但其中一定存在一个对算法执行时间起主要作用的原操作，称这种原操作为”基本操作”，换句话说，算法的执行时间主要取决于”基本操作“的重复次数。 由于算法的时间复杂度是算法执行时间增长率的量度（其随问题规模的增长而“增长的趋势” ），因此在计算算法的时间复杂度只需要考虑在算法中“起主要作用”的“基本操作”的重复次数即可，而其他原操作的重复次数相对“基本操作”来说或者是一个常量或者变化率很小，可以忽略。 “基本操作”的重复执行次数和算法的执行时间成正比。 * 容易看出，算法中的控制结构是三重循环，每一重循环的次数是 n 。原操作有赋值，加法和乘法，显然，在三重循环之内的“乘法”是基本操作，它的重复执行次数是n3。 因此，算法的时间复杂度: O(n3) * 2.4. ???? i=1;?????? ①??? while (i=n)?????? i=i*2; ②解： 语句1的频度是1,?