chap_01_font_embedded1讲解.ppt

定义: 给定两个非负函数f(n) 和 g(n), 如果存在一个正整数n0 以及一个常数k0 使得f(n)≤kg(n) 对于任意n≥n0 的正整数都成立，那么我们说f(n)=O(g(n)), 关于“Big Oh” 使用正确的“Big Oh”表示 如果f(n) 是一个d次多项式，那么f(n) 是 O(nd) 基本原则： 舍弃低阶项 舍弃常数系数 使用最低的可能数量级 –正确：“100n 是O(n)” ，错误：“100n 是O(n2)” 使用最简标注 – 正确：“3n + 5 是 O(n)” ，错误：“3n + 5 是 O(3n)” void mult(int a[], int b[], int c[] ) { // 以二维数组存储矩阵元素，c 为 a 和 b 的乘积 for (i=1; i=n; ++i){ for (j=1; j=n; ++j) { c[i,j] = 0; for (k=1; k=n; ++k) c[i,j] += a[i,k]*b[k,j]; } //for }//for } //mult 基本操作？ 时间复杂度的O（f(n)）表示？ 例2：冒泡排序法。 void bubble_sort(int a[]，int n) { for (i=n-1，change=TURE; i1 change; --i) change=false; for (j=0; ji; ++j) if (a[j]a[j+1]) {a[j] ←→a[j+1] ; change=TURE ; } } 最好情况：0次 最坏情况：1+2+3+?+n-1=n(n-1)/2 平均时间复杂度为： O(n2) 四、算法的存储空间需求 算法的空间复杂度定义为: 表示随着问题规模 n 的增大， 算法运行所需存储量的增长率 与 g(n) 的增长率相同。 S(n) = O(g(n)) 算法的存储量包括: 1．输入数据所占空间 2．程序本身所占空间； 3．辅助变量所占空间。 若输入数据所占空间只取决与问题 本身，和算法无关，则只需要分析除 输入和程序之外的辅助变量所占额外 空间。 若所需额外空间相对于输入数据量 来说是常数，则称此算法为原地工作。 若所需存储量依赖于特定的输入， 则通常按最坏情况考虑。 1. 熟悉各名词、术语的含义，掌握基本概念。 2. 理解算法五个要素的确切含义。 本章学习要点 3. 掌握计算语句频度和估算算法时间复杂度的方法。 Hints Should I memorize all the codes? 理解规律，尊重规律 2011 by Fang, Can * Case Study: π π = 3.1415926535897932384626433832795028841991693993751058209749445923078164062862089986280348253421170679…… 山巅一寺一壶酒（3.14159），尔乐苦煞吾（26535），把酒吃（897），酒伤尔（932），伤不死（384），乐尔乐（626） 2011 by Fang, Can * 作业题 请用“big Oh”表示x=x+1的执行次数： for i=1 to n for j=1 to i for k=1 to j x = x +1； 具体的算法是：1+(1+2)+(1+2+3)+...+(1+2+...+n) 你可以举个例子，比如n=4时，i从1到n?三层循环中的循环变量是如何变化的。 ? 上面的公式可以转换成关于n的表达式，应该是 n(n+1)(n+2)/6 2011 by Fang, Can * 2. 下列函数的时间复杂度为多少？ void Unknown(int m, int n) { int i, j; for(i = 1; i=m; i++){ j=1; while(j=n){ j*=2; } } } 2011 by Fang, Can * Algorithm Mystery(n) //输入n 是一个正整数 s = 0； for (i= 1, i=n, i++) s = s + i × i； return s 算法完成了何种任务？ 基本操作运行的次数？ 算法的复杂