值操作,其渐进复杂度为O(n) 随着循环中嵌套循环,其时间复杂度会相应增大。例如,下面这段代码依次求出给定数 组的所有子数组中各元素之和 for(i=0; i<n; i++) for(=1,sum=a[0;j<=;j++) sum +=all 循环开始前,有一次对i的赋值操作。之后,外层循环共进行n次,每个循环中包含 个内层循环,以及对i,j,sum分别进行赋值的操作;每个内层循环执行2个赋值操作,分 别更新sum和j;共执行i次(i=1,2,…,n-1)。所以,整个程序总共执行的赋值操作为 +3n+∑2=1+3n+2(1+2+…+n-1)=1+3n+n(n-1)=O)+On2)=O(n2)° 一般情况下,循环中嵌套循环会增加算法的时间复杂度,但也并非总是如此。例如,在 上面的实例中,如果只对每个子数组的前5个元素求和,则相应的代码可采用下面的方式 for(F4; K<n; 1++) for(=|-3,sum=a[i-4;j<=i,j++) sum +=all: 此时,外层循环进行n-4次。对每个i而言,内层循环只执行4次,每次的操作次数与 的大小无关:8次赋值操作。外加对i的初始化,整个代码总共进行O(1)+8(n-4)=O(n)次 赋值操作。尽管存在嵌套循环,但算法的整体时间复杂度依然呈线性增长 关键是通过这些案例让学生领会和掌握基本的算法分析方法。 8.总结 概论是《数据结构与算法》课程提纲挈领的一章,是帮助学生了解课程目标、把握课程 基本内容和方法的重要环节 除了上述教学注意事项之外。还需要提醒学生注意实际应用,针对同一个问题一般会存 在多种算法,这些算法在时间和空间开销上的优劣往往表现出“时空折衷”的性质。需要根 据应用的具体情况,在设计或选择数据结构时进行适当的权衡。 参考文献: 1.张铭,王腾蛟,赵海燕,《数据结构与算法》,高等教育出版社,2008年6月。—普 通高等教育“十一五”国家级规划教材 2.张铭、赵海燕、王腾蛟、宋国杰、高军,北京大学“数据结构与算法”教学设计,《计 算机教育》2008第20期。获得“英特尔杯2008年全国计算机教育优秀论文评比”一等 奖 3.北京大学《数据结构与算法》精品课程网站(2008年北京市“精品课程”暨国家“精品 课程),http://www.jpk.pkueducn/pkujpk/course/sjjg/ 4.蒋宗礼,“编译原理教学设计”。《计算机教育》,2008.3。 5.张铭、许卓群、杨冬青、唐世渭,“数据结构知识系统及教学实践”。《计算机教育》。《计 算机教育》,2004年2、3月合刊,PP89-91。值操作，其渐进复杂度为 O(n) 。 随着循环中嵌套循环，其时间复杂度会相应增大。例如，下面这段代码依次求出给定数 组的所有子数组中各元素之和： for (i = 0; i < n; i++) for (j = 1, sum = a[0]; j <= i; j++) sum += a[j]; 循环开始前，有一次对 i 的赋值操作。之后，外层循环共进行 n 次，每个循环中包含一 个内层循环，以及对 i，j，sum 分别进行赋值的操作；每个内层循环执行 2 个赋值操作，分 别更新 sum 和 j；共执行 i 次（i=1,2, …,n-1）。所以，整个程序总共执行的赋值操作为： n 1 2 2 i 1 1 3n 2i 1 3n 2(1 2 .... n 1) 1 3n n(n 1) O(n) O(n ) O(n )                    。 一般情况下，循环中嵌套循环会增加算法的时间复杂度，但也并非总是如此。例如，在 上面的实例中，如果只对每个子数组的前 5 个元素求和，则相应的代码可采用下面的方式： for ( i=4; i<n; i++) for (j = i-3, sum = a[i-4]; j <= i; j++) sum += a[j]; 此时，外层循环进行 n-4 次。对每个 i 而言，内层循环只执行 4 次，每次的操作次数与 i 的大小无关：8 次赋值操作。外加对 i 的初始化，整个代码总共进行 O(1) + 8(n-4) = O(n)次 赋值操作。尽管存在嵌套循环，但算法的整体时间复杂度依然呈线性增长。 关键是通过这些案例让学生领会和掌握基本的算法分析方法。 8．总结 概论是《数据结构与算法》课程提纲挈领的一章，是帮助学生了解课程目标、把握课程 基本内容和方法的重要环节。 除了上述教学注意事项之外。还需要提醒学生注意实际应用，针对同一个问题一般会存 在多种算法，这些算法在时间和空间开销上的优劣往往表现出“时空折衷”的性质。需要根 据应用的具体情况，在设计或选择数据结构时进行适当的权衡。 参考文献： 1. 张铭，王腾蛟，赵海燕，《数据结构与算法》，高等教育出版社，2008 年 6 月。——普 通高等教育“十一五”国家级规划教材。 2. 张铭、赵海燕、王腾蛟、宋国杰 、高军，北京大学“数据结构与算法”教学设计，《计 算机教育》2008 第 20 期。获得“英特尔杯 2008 年全国计算机教育优秀论文评比”一等 奖。 3. 北京大学《数据结构与算法》精品课程网站（2008 年北京市“精品课程”暨国家“精品 课程”）， http://www.jpk.pku.edu.cn/pkujpk/course/sjjg/ 4. 蒋宗礼，“编译原理教学设计”。《计算机教育》, 2008.3。 5. 张铭、许卓群、杨冬青、唐世渭，“数据结构知识系统及教学实践”。《计算机教育》。《计 算机教育》，2004 年 2、3 月合刊，PP89-91