Chapter 2 Program Performance Introduction Space Complexity Time Complexity Asymptotic Notation Practical Complexities Performance Measurement 12/4/2018

本章重点 顺序搜索/折半搜索算法 名次排序/选择排序/冒泡排序/插入排序算法 渐进符号（O、Θ 、Ω 、o） 12/4/2018

算法的性能标准 正确性 可使用性 可读性 健壮性 文档 效率：对空间和时间的需求 12/4/2018

2.1 Program Performance 程序性能:运行一个程序所需要的内存和时间。 为什么关心程序性能？ 分析(Analysis)/实验(measurement) 空间复杂性(Space Complexity)/时间复杂性(Time Complexity) 12/4/2018

2.2 Space Complexity 指令空间(Instruction space) 数据空间(Data space) 环境栈空间(Environment stack space) 12/4/2018

指令空间 程序所需要的指令空间的数量取决于如下因素： 把程序编译成机器代码的编译器。 编译时实际采用的编译器选项。 目标计算机。 例子: 计算表达式a+b+b*c+(a+b-c)/(a+b)+4 的代码。 12/4/2018

12/4/2018

数据空间 对于简单变量和常量来说，所需要的空间取决于所使用的计算机和编译器以及变量与常量的数目。 由于每字节所占用的位数依赖于具体的机器环境，因此每个变量所需要的空间也会有所不同。 12/4/2018

环境栈空间 每当一个函数被调用时，下面的数据将被保存在环境栈中： 返回地址。 函数被调用时所有局部变量的值以及传值形式参数的值（仅对于递归函数而言）。 所有引用参数及常量引用参数的定义。 12/4/2018

结论 无法精确地分析一个程序所需要的空间。 可以确定程序中某些部分的空间需求，这些部分依赖于所解决实例的特征。 例：对n 个元素进行排序；累加两个n×n 矩阵；累加两个m×n 矩阵。 12/4/2018

递归栈空间 递归函数所需要的栈空间通常称之为递归栈空间（recursion stack space）。 对于每个递归函数而言，该空间主要依赖于局部变量及形式参数所需要的空间。除此以外，该空间还依赖于递归的深度（即嵌套递归调用的最大层次）。 12/4/2018

空间复杂性度量 可以把一个程序所需要的空间分成两部分： 固定部分，独立于实例的特征。一般来说，这一部分包含指令空间（即代码空间）、简单变量及定长复合变量所占用空间、常量所占用空间等等。 可变部分，由以下部分构成：复合变量所需的空间（这些变量的大小依赖于所解决的具体问题），动态分配的空间（这种空间一般都依赖于实例的特征），以及递归栈所需的空间（该空间也依赖于实例的特征）。 12/4/2018

空间复杂性度量 任意程序P 所需要的空间S（P）可以表示为： S(P) = c + Sp（实例特征） 12/4/2018

程序2-1 顺序搜索(Sequenial Search) template<class T> int SequentialSearch(T a[], const T& x, int n) {//在未排序的数组a[0:n-1]中搜索x，如果找到，则返回所在位置，否则返回- 1 int i; for (i = 0; i < n && a[i] != x; i++); if (i == n) return -1 ; return i; } 12/4/2018

顺序搜索的空间复杂性分析 采用实例特征n 来估算该函数的空间复杂性。 假定T 为int 类型，则数组a 中的每个元素需要2个字节，实参x需要2个字节，传值形式参数n 需要2个字节，局部变量i 需要2个字节，每个整型常量0和-1也分别需要2个字节。因此，所需要的总的数据空间为12字节。 因为该空间独立于n，所以S顺序搜索（n）= 0。 12/4/2018

程序1-8 空间复杂性分析 template<class T> T Sum(T a[],int n) {//计算a[0:n-1]的和 T tsum = 0; for(int i=0;i<n;i++) tsum += a[i]; return tsum; } SSum (n) = ? 12/4/2018

程序1-9 空间复杂性分析 template<classT> TRsum(T a[],int n) {//计算a[0:n-1]的和 if(n>0) return Rsum(a,n-1)+a[n-1]; return 0; } 12/4/2018

程序1-9 空间复杂性分析 每一次调用Rsum 需要6个字节的栈空间。 由于递归的深度为n+1，所以需要6(n+1)字节的递归栈空间，因而SRsum(n)=6(n+1)。 12/4/2018

阶乘 空间复杂性分析 程序1-7计算n！的递归函数 int Factorial(int n) {//计算n！ if(n<=1) return 1; return n*Factorial(n-1); } SFactorial(n)=? 12/4/2018

排列 空间复杂性分析 template<class T> Void Perm(T list[],int k,int m) {//生成list[k：m]的所有排列方式 int i; if(k == m){//输出一个排列方式 for(i=0;i<=m;i++) cout<<list[i]; cout<<endl; } else//list[k：m]有多个排列方式，递归地产生这些排列方式 for(i=k;i<=m;i++){ Swap(list[k],list[i]); Perm(list,k+1,m); } SPerm (n) = ? 12/4/2018

执行顺序搜索的递归函数 template <class T> int SequentialSearch(T a[], const T& x, int n) { //在未排序的数组a [ 0 : n-1 ]中查找x //如果找到则返回所在位置，否则返回- 1 if (n<1) return -1 ; if (a[n-1] == x) return n-1 ; return SequentialSearch(a,x,n-1 ) ; } SP (n) = ? 12/4/2018

2.3 Time Complexity 为了比较两个完成同一功能的程序的时间复杂性； 为了预测随着实例特征的变化，程序运行时间的变化量。 12/4/2018

时间复杂性 一个程序P所占用的时间T(P)=编译时间+运行时间。 12/4/2018

估算运行时间方法 精确困难？ 找出一个或多个关键操作(对时间复杂性的影响最大)，确定这些关键操作所需要的执行时间； 确定程序总的执行步数。 12/4/2018

操作计数Operation Counts 求最大元素 多项式求值(Polynomial evaluation) 按名次排序(Rank sort) 选择排序(Selection sort) 冒泡排序(Bubble sort) 插入排序(Insertion sort) 顺序搜索(Sequential search) 名次排序优化/选择排序优化/冒泡排序优化 12/4/2018

程序1-31 寻找最大元素 template<class T> int Max(T a[], int n) {// 寻找a [0 : n-1]中的最大元素 int pos = 0; for (int i = 1; i < n; i++) if (a[pos] < a[i]) pos = i; return pos; } 每次调用Max(a,n)需要执行n-1次比较。 12/4/2018

多项式求值 12/4/2018

程序2-3多项式求值算法 template <class T> T PolyEval(T coeff[], int n, const T& x) { / /计算n次多项式的值，coeff[0:n]为多项式的系数 T y=1, value= coeff[0] ; for ( int i = 1; i <= n; i++) { //累加下一项 y *= x; value += y * coeff[i] ; } return value; 12/4/2018

多项式求值算法时间复杂性 使用维数n 作为实例特征。 假定根据for循环内部所执行的加和乘的次数来估算时间复杂性。 进入for循环的总次数为n，每次循环执行1次加法和2次乘法（这种操作计数不包含循环控制变量i 每次递增所执行的加法）。 加法的次数为n，乘法的次数为2n。 12/4/2018

多项式求值优化 Horner 法则采用如下的分解式计算一个多项式： P(x)=(…(cn*x+cn-1)*x+cn-2)*x+cn-3)*x+…)*x+c0 12/4/2018

程序2-4 利用Horner 法则对多项式进行求值 template <class T> T Horner(T coeff[], int n, const T& x) { //计算n次多项式的值，coeff[0 : n]为多项式的系数 T value= coeff [n] ; for( int i = 1; i <= n; i++) value = value * x + coeff[n-i] ; return value; } 12/4/2018

比较 可以估算出该程序的时间复杂性为n 次加法和n 次乘法。 由于函数PolyEval 所执行的加法次数与Horner 相同，而乘法次数是Horner的两倍，因此，函数 Horner 应该更快。 12/4/2018

计算名次 元素在队列中的名次(rank)可定义为队列中所有比它小的元素数目加上在它左边出现的与它相同的元素数目。 例如，给定一个数组a=[4, 3, 9, 3, 7]作为队列，则各元素的名次为r=[2,0,4,1,3]。 12/4/2018

程序2-5 计算名次 template <class T> void Rank(T a[], int n, int r[]) { //计算a [0:n-1]中n个元素的排名 for (int i = 0; i < n; i++) r[i] = 0; //初始化 //逐对比较所有的元素 for (int i = 1; i < n; i++) for ( int j = 0; j < i; j++) if (a [j] <= a[ i]) r[i]++; else r[j ]++; } 12/4/2018

计算名次时间复杂性 根据a的元素之间所进行的比较操作来估算程序的时间复杂性。 对于i的每个取值，执行比较的次数为i,所以总的比较次数为1+2+3+ … +n-1 = (n-1)n/2。 12/4/2018

名次排序Rank Sort/计数排序 程序2-6 利用附加数组重排数组元素 template <class T> void Rearrange (T a[], int n, int r[]) { //按序重排数组a中的元素，使用附加数组u T *u = new T[n+1]; //在u中移动到正确的位置 for (int i = 0; i < n; i++) u[r[i]] = a[i]; //移回到a中 a[i] = u[i] ; delete [ ]u; } 12/4/2018

名次排序Rank Sort性能 比较操作次数 = (n-1）n/2 移动操作次数 = 2n 12/4/2018

优化名次排序Rank Sort template <class T> void Rearrange (T * &a, int n, int r[]) { //按序重排数组a中的元素，使用附加数组u T *u = new T[n+1]; //在u中移动到正确的位置 for ( int i = 0; i < n; i++) u[r[i]] = a[i]; delete [ ]a; a=u; } 12/4/2018

选择排序 selection sort 思想：首先找出最大的元素，把它移动到a[n-1]，然后在余下的n-1个元素中寻找最大的元素并把它移动到a[n-2]，如此进行下去。 12/4/2018

程序1-31 寻找最大元素 template<class T> int Max(T a[], int n) {// 寻找a [0 : n-1]中的最大元素 int pos = 0; for (int i = 1; i < n; i++) if (a[pos] < a[i]) pos = i; return pos; } 每次调用Max(a,size)需要执行size-1次比较。 12/4/2018

选择排序算法实现 template <class T> void SelectionSort (T a[], int n) { //对数组a [0:n-1]中的n个元素进行排序 for ( int size = n; size > 1; size- -) { int j= Max(a, size); //size-1次比较 Swap( a[j],a[size-1] ) ; //移动3次 } 12/4/2018

选择排序时间复杂性 按照元素的比较次数来估算函数的时间复杂性。 每次调用Max(a,size)需要执行size-1次比较，所以总的比较次数为1+2+3+…+n-1= (n-1)n/2。元素的移动次数为3(n-1)。 比较操作次数 = (n-1）n/2 移动操作次数 = 3(n-1) 与名次排序比较。 12/4/2018

冒泡排序 bubble sort 采用一种“冒泡策略”把最大元素移到右部。在冒泡过程中，对相邻的元素进行比较，如果左边的元素大于右边的元素，则交换这两个元素。 在一次冒泡过程结束后，可以确信最大的元素肯定在最右边的位置上。 例:[ 5 , 3 , 7 , 1 ]，在第一次冒泡过程结束后，得到？ 12/4/2018

程序2-8 一次冒泡 template <class T> void Bubble (T a[], int n) { //把数组a[0:n-1]中最大的元素通过冒泡移到右边 for ( int i = 0; i < n-1; i++) if(a[i]>a[i+1]) Swap(a[i],a[i+1]); } 12/4/2018

冒泡排序 template <class T> void BubbleSort (T a[], int n) {//对数组a[0:n-1]中的n个元素进行冒泡排序 for ( int i = n; i>1; i- -) Bubble(a,i) ; } 12/4/2018

冒泡排序时间复杂性 比较操作次数 = (n-1)n/2 移动操作次数 = 0 最好 = 3(n-1)n/2 最坏。 12/4/2018

最好、最坏和平均操作数 12/4/2018

顺序搜索成功查找的平均比较次数 template<class T> int SequentialSearch(T a[], const T& x, int n) { int i; for (i = 0; i < n && a[i] != x; i++); if (i == n) return -1 ; return i; } 假定每个元素被查找的概率是相同的 =? 12/4/2018

向有序数组中插入元素 向有序数组a[0:n-1]中插入一个元素。a中的元素在执行插入之前和插入之后都是按递增顺序排列的。 例如，向数组a[0:5] = [1,2,6,8,9,11]中插入4，得到的结果为a[0:6]=[1,2, 4,6,8,9,11]。 当为新元素找到欲插入的位置时，必须把该位置右边的所有元素分别向右移动一个位置。对于本例，需要移动11,9,8和6，并把4插入到新空出来的位置a[2]中。 12/4/2018

程序2-10 向一个有序数组中插入元素 template<class T> void Insert(T a[], int& n, const T& x) { // 向有序数组a [0:n-1]中插入元素x // 假定a 的大小超过n int i; for (i=n-1;i>=0 &&x<a[i];i--) a[i+1] = a[i]; a[i+1] = x; n++; // 添加了一个元素 } 平均比较次数？ 12/4/2018

平均比较次数 假定x 有相等的机会被插入到任一个可能的位置上（共有n + 1个可能的插入位置）。 如果x 最终被插入到a的i+1处，i≥0，则执行的比较次数为n-i。如果x 被插入到a[0]，则比较次数为n。所以平均比较次数为： 12/4/2018

优化名次排序 2-6名次排序的缺点？ void Rearrange (T * &a, int n, int r[]) { T *u = new T[n+1]; for ( int i = 0; i < n; i++) u[r[i]] = a[i]; delete [ ]a; a=u; } 12/4/2018

优化名次排序-原地重排 从a[0] 开始，每次检查一个元素。 如果当前正在检查的元素为a[i] 且r[i]= i，那么可以跳过该元素，继续检查下一个元素； 如果r[i]≠i, 可以把a[i]与a[r[i]] 进行交换，交换的结果是把原a[i] 中的元素放到正确的排序位置（r[i]）上去。这种交换操作在位置i 处重复下去，直到应该排在位置i 处的元素被交换到位置i处。 之后，继续检查下一个位置。 12/4/2018

优化名次排序-原地重排 程序2 - 11 原地重排数组元素 template<class T> void Rearrange(T a[], int n, int r[]) { // 原地重排数组元素 for (int i = 0; i < n; i++) // 获取应该排在a[i]处的元素 while (r[i]!= i) { int t = r[i]; Swap(a[i], a[t]); Swap(r[i], r[t]); } } 最少交换次数 ?，最大的交换次数 ? 12/4/2018

名次排序性能(额外空间) 最好情况：数组a最初已经有序。 最坏情况：数组a 23451或 51234。。。 最好 最坏 最好 最坏 比较 n(n-1)/2+n n(n-1)/2+n 移动 0 6(n-1) 12/4/2018

优化选择排序 2-7选择排序的缺点？ void SelectionSort (T a[], int n) { for ( int size = n; size > 1; size- -){ int j= Max(a, size); Swap( a[j],a[size-1] ) ; } 12/4/2018

优化选择排序 程序2-7中选择排序函数的一个缺点是：即使元素已经按序排列，程序仍然继续运行。 为了终止不必要的循环，在查找最大元素期间，可以顺便检查数组是否已按序排列。 12/4/2018

程序2-12 及时终止的选择排序 template<class T> void SelectionSort(T a[], int n) { // 及时终止的选择排序 bool sorted = false; for(int size = n; !sorted && (size > 1);size--) { int pos = 0; sorted = true; // 找最大元素 for (int i = 1; i < size; i++) if (a[pos] <= a[i]) pos = i; else sorted = false; // 未按序排列 Swap(a[pos], a[size - 1 ] ) ; } 最坏情况下比较次数，移动次数 ? } 最好情况下比较次数，移动次数 ? 12/4/2018

选择排序性能 最好情况：数组a有序。 最坏情况：数组a最大元素在首位，其他与元素 已经有序。 最好 最坏 比较 n-1 n(n-1)/2 最好 最坏 比较 n-1 n(n-1)/2 移动 3 3(n-1) 12/4/2018

优化冒泡排序 2-9冒泡排序的缺点？ void Bubble (T a[], int n) { for ( int i = 0; i < n-1; i++) if(a[i]>a[i+1]) Swap(a[i],a[i+1]); } void BubbleSort (T a[], int n) for ( int i = n; i>1; i- -) Bubble(a,i) ; 12/4/2018

优化冒泡排序 如果在一次冒泡过程中没有发生元素互换，则说明数组已经按序排列，没有必要再继续进行冒泡过程。 12/4/2018

程序2-13 及时终止的冒泡排序 template<class T> bool Bubble(T a[], int n) { //把a[0:n-1] 中最大元素冒泡至右端 bool swapped = false; // 尚未发生交换 for (int i = 0; i < n - 1; i++) if (a[i] > a[i+1]) { Swap(a[i], a[i+1]); swapped = true; // 发生了交换 } return swapped; 12/4/2018

程序2-13 及时终止的冒泡排序 最坏情况下比较次数，移动次数 ? 最好情况下比较次数，移动次数 ? template<class T> void BubbleSort(T a[], int n) {// 及时终止的冒泡排序 for(int i = n;i>1 && Bubble(a,i);i- -) ; } 最坏情况下比较次数，移动次数 ? 最好情况下比较次数，移动次数 ? 12/4/2018

冒泡排序性能 最好情况：数组a最初已经有序。 最坏情况：数组a倒序。 最好 最坏 比较 n-1 n(n-1)/2 最好 最坏 比较 n-1 n(n-1)/2 移动 0 3*n(n-1)/2 12/4/2018

插入排序Insertion Sort 思想：因为只有一个元素的数组是一个有序数组，所以可以从包含n个元素的数组的第一个元素开始。通过把第二个元素插入到这个单元数组中，可以得到一个大小为2的有序数组。插入第三个元素可以得到一个大小为3的有序数组。 按照这种方法继续进行下去，最终将得到一个大小为n的有序数组。 12/4/2018

插入排序 template<class T> void Insert(T a[], int n, const T& x) {// 向有序数组a [ 0 : n - 1 ]中插入元素x for (int i=n-1; i >= 0 && x < a[i]; i- -) a[i+1]=a[i]; a[i+1]=x; } void InsertionSort(T a[], int n) {// 对a [0:n-1]进行排序 for (int i=1; i < n; i++) { T t=a[i]; //? Insert(a, i, t); } 12/4/2018

程序2-15 另外一种插入排序 template<class T> void InsertionSort(T a[], int n) { for (int i=1; i < n; i++) { //将a[i]插入a [ 0 : i-1 ] T t=a[i]; int j; for (j=i-1;j >= 0 && t<a[j]; j--) a[j+1]=a[j]; a[j+1]=t; }最坏情况下比较次数? 移动次数？ } 最好情况下比较次数? 移动次数？ 12/4/2018

插入排序性能 最好情况：数组a最初已经有序。 最坏情况：数组a倒序。 最好 最坏 比较 n-1 n(n-1)/2 最好 最坏 比较 n-1 n(n-1)/2 移动 n-1 n-1+n(n-1)/2 12/4/2018

排序算法比较 算法 最好 最坏 名次排序 比较 n(n-1)/2+n n(n-1)/2+n 移动 0 6(n-1) 算法 最好 最坏 名次排序 比较 n(n-1)/2+n n(n-1)/2+n 移动 0 6(n-1) 选择排序 比较 n-1 n(n-1)/2 移动 3 3(n-1) 冒泡排序 比较 n-1 n(n-1)/2 移动 0 3*n(n-1)/2 插入排序 比较 n-1 n(n-1)/2 移动 n-1 n-1+n(n-1)/2 12/4/2018

执行步数Step Counts 利用操作计数方法来估算程序的时间复杂性忽略了所选择操作之外其他操作的开销。 在统计执行步数的方法中，要统计程序/函数中所有部分的时间开销。 与操作计数一样，执行步数也是实例特征的函数。 12/4/2018

程序步program step 程序步可以定义为一个语法或语义意义上的程序片段，该片段的执行时间独立于实例特征。 可以通过创建一个全局变量count 来确定一个程序或函数为完成其预定任务所需要的执行步数。 把count 引入到程序语句之中，每当原始程序或函数中的一条语句被执行时，就为count 累加上该语句所需要的执行步数。当程序或函数运行结束时所得到的count的值即为所需要的执行步数。 12/4/2018

程序2-16 统计程序1 - 8的执行步数 template<class T> T Sum(T a[], int n) {// 计算a[0:n - 1]中元素之和 T tsum=0; count++; // 对应于tsum=0 for (int i=0; i < n; i++) { count++; // 对应于for语句 tsum += a[i]; count++; // 对应于赋值语句 } count++; // 对应于最后一个for语句 count++; //对应于return语句 return tsum; } count=? 12/4/2018

分析 Sum 的每次调用需要执行2n+3步。 12/4/2018

程序2-18 统计程序1-9的执行步数 template<class T> T Rsum(T a[], int n) { //计算a[0:n - 1]中元素之和 count++; // 对应于if 条件 if(n>0){ count++;//对应于return和Rsum 调用 return Rsum(a,n-1)+a[n-1]; } count++; //对应于return return 0; } count=? 12/4/2018

分析 令tRsum(n)为程序Rsum结束时count所增加的值，可以看出tRsum(0)=2。当n>0时，count所增加的值为2加上调用函数Rsum所增加的值。 从tRsum(n)的定义可知，额外的增值为tRsum(n-1)。所以，如果count的初值为0，在程序结束时它的值将变成2+tRsum(n-1)，其中n>0。 12/4/2018

分析 在分析一个递归程序的执行步数时，通常可以得到一个计算执行步数的递归等式(如tRsum(n)=2+tRsum(n-1)，n>0且tRsum(2)=0)。 这种递归公式被称为递归等式(recurrence equation) 。 可以采用重复迭代的方法来计算递归等式，如:tRsum(n)=2+tRsum(n-1)=2+2+tRsum(n-2)=4 +tRsum(n-2)...=2n+tRsum(0)=2(n+1) 其中n≥0，因此函数Rsum的执行步数为2(n+1)。 12/4/2018

比较 比较程序Sum和程序RSum的执行步数，可以看到程序RSum的执行步数(2n+2)小于程序Sum的执行步数(2n+3)。 不过不能因此断定程序Sum就比程序RSum慢，因为程序步不代表精确的时间单位。Rsum中的一步可能要比Sum中的一步花更多的时间，所以Rsum有可能要比Sum慢。 12/4/2018

执行步数 执行步数可用来帮助我们了解程序的执行时间是如何随着实例特征的变化而变化的。 从Sum的执行步数中可以看到，如果n 被加倍，程序运行时间也将加倍(近似地)；如果n增加10倍，运行时间也会增加10倍。 所以可以预计，运行时间随着n 线性增长。 称Sum是一个线性程序(其时间复杂性与实例特征n 呈线性关系)。 12/4/2018

执行步数表 如果不想使用count计值语句，可以建立一张表，在该表中列出每条语句所需要的执行步数。 建立这张表时，可以首先确定每条语句每一次执行所需要的步数以及该语句总的执行次数(即频率)，然后利用这两个量就可以得到每条语句总的执行步数，把所有语句的执行步数加在一起即可得到整个程序的执行步数。 12/4/2018

程序2-19矩阵加法 把存储在二维数组a[0:rows-1][0:cols-1]和b[0:rows-1][0:cols-1]中的两个矩阵相加。 template<class T> void Add(T **a,T **b,T **c,int rows,int cols) {//矩阵a和b相加得到矩阵c. for(int i=0;i<rows;i++) for(int j=0;j<cols;j++) c[i][j]=a[i][j]+b[i][j]; } 12/4/2018

程序2-20统计程序2-19的执行步数 template<class T> void Add(T **a,T **b,T **c,int rows,int cols) {//矩阵a和b相加得到矩阵c. for(int i=0;i<rows;i++){ count++;//对应于上一条for语句 for(int j=0;j<cols;j++){ c[i][j]=a[i][j]+b[i][j]; count++;//对应于赋值语句 } count++;//对应j的最后一次for循环 } count++;//对应i的最后一次for循环 } count? 12/4/2018

分析 count的值为2rows*cols+2rows+1。 如果rows>cols，提高性能方案？ 12/4/2018

s/e 语句每次执行所需要的步数通常记为s/e，一条语句的s/e就等于执行该语句所产生的count值的变化量。 12/4/2018

执行步数表 一条语句的程序步数与该语句每次执行所需要的步数(s/e)之间有重要的区别，区别在于程序步数不能反映该语句的复杂程度。 例如语句：x=Sum(a,m);的程序步数为1，而该语句的执行所导致的count值的实际变化为1加上调用Sum所导致的count值的变化(2m + 3)之和，因此该语句每次执行所需要的步数为1+2m+3=2m+4。 12/4/2018

12/4/2018

12/4/2018

12/4/2018

矩阵转置 b是a的转置，当且仅当对于所有的i和j，有b[i][j]=a[j][i] 12/4/2018

程序2-22矩阵转置 template<class T> void Transpose(T **a,int rows) {//对矩阵a[0:rows-1][0:rows-1]进行转置 for(int i=0;i<rows;i++) for(int j=i+1;j<rows;j++) Swap(a[i][j],a[j][i]); } 12/4/2018

12/4/2018

2.4 Asymptotic Notation Big Oh Notation Omega Notation Theta Notation Little Oh 12/4/2018

引入渐进符号的目的 希望能比较算法的运行时间和空间需求，并使这种比较能与程序设计语言、编译系统、机器结构、处理器的速度以及系统的负载等复杂因素无关。 12/4/2018

分析 操作计数和执行步数都不能够非常精确地描述时间复杂性。 由于执行步数的不精确性，所以不便于用来进行比较。 如果有两个程序的时间复杂性分别为c1n2+c2n和c3n，那么可以知道，对于足够大的n，不管c1、c2和c3的值是多少，复杂性为c3n 的程序将比复杂性为c1n2+c2n的程序运行得快。 12/4/2018

渐进符号 渐进符号，描述大型实例特征下时间或空间复杂性的具体表现。 在下面的讨论中f(n)表示一个程序的时间或空间复杂性，它是实例特征n的函数。 12/4/2018

Big Oh Notation 大写O 符号给出了函数f的一个上限。 定义: f(n)=O(g(n)) 当且仅当存在正的常数c 和n0，使得对于所有的n≥n0,有f(n)≤cg(n)。 12/4/2018

解释 O表示量级(Order)。(最坏情况) O(g(n))表示当n增大时，运行时间至多将以正比于g(n)的速度增长。 最小上限 12/4/2018

常用的g函数及其名称 函数 名称 1 常数 logn 对数 n 线性 nlogn n个logn n2 平方 n3 立方 2n 指数 函数 名称 1 常数 logn 对数 n 线性 nlogn n个logn n2 平方 n3 立方 2n 指数 n! 阶乘 12/4/2018

线性函数 考察f(n)= 3n+2。 当n≥ n0 =2时，3n+2≤3n+n＝4n，所以f(n)=O(n)，f(n)是一个线性变化的函数。 类似地，对于f(n)=100n+6,当 n≥n0=6，有f(n)=100n+6≤ 100n+n=101n，因此，100n+6=O(n)。 12/4/2018

平方函数 考察f(n)=10n2+4n+2。 对于n≥2,有f(n)≤10n2+5n。由于当n≥5时有5n≤n2，因此对于n≥n0 = 5，f(n)≤10n2+n2 =11n2 ，所以f(n)=O(n2)。 12/4/2018

指数函数 考察f(n)=6*2n+n2 。 可以观察到对于n≥4，有n2≤2n，所以对于n≥4，有f(n)≤ 6*2n+2n=7*2n，因此6*2n+n2=O(2n)。 12/4/2018

常数函数 当f(n)是一个常数时，比如f(n)=9，可以记为f(n)=O(1)。 这种写法的正确性很容易证明。例如，对于f(n)=9≤9*1，只要令c=9 以及n0=0 即可得f(n)=O(1)。 12/4/2018

推导策略 用次数高的项目（如n2）替换次数低的项目（如n），直到剩下一个单项为止。 12/4/2018

结论 语句f(n)=O (g(n)) 仅表明对于所有的n≥n0 ，cg(n)是f(n)的一个上限。它并未指出该上限是否为最小上限。 为了使语句f(n)=O(g(n))有实际意义，其中的g(n)应尽量地小。因此常见的是3n+3=O(n),而不是3n+3=O (n2)，尽管后者也是正确的。 12/4/2018

有用的结论 定理2-1 如果f(n)=amnm+ … +a1n+a0 且am>0，则f(n)=O(nm)。 12/4/2018

加法规则 T(n)=T1(n)+T2(n) =O(g1(n)) + O(g2(n)) =O(max(g1(n),g2(n))) 12/4/2018

乘法规则 T(n)=T1(n)*T2(n) =O(g1(n)) * O(g2(n)) =O(g1(n)*g2(n)) 12/4/2018

void exam ( float x[ ][ ], int m, int n ) { float sum [ ]; for (int i=0;i<m;i++) {//x中各行数据累加 sum[i] = 0.0; for (int j = 0; j<n; j++) sum[i] += x[i][j]; } for (i=0; i<m; i++) //打印各行数据和 cout << i << “ : ” <<sum [i] << endl; 时间复杂度为 O(max (m*n, m)) 12/4/2018

作用 采用大O表示法简化了时间和空间代价的度量，其基本思想是主要关注复杂性的量级，而忽略量级的系数，使我们在分析算法的复杂度时，可忽略零星变量的存储开销和循环外个别语句的执行时间，重点分析算法的主要代价。 12/4/2018

Omega Notation Ω 符号用来估算函数f 的下限值。 定义 f(n)=Ω(g(n)) 当且仅当存在正的常数c 和n0，使得对于所有的n≥n0，有f(n)≥cg(n)。 12/4/2018

例子 对于所有的n，有f(n)=3n+2>3n，因此f(n)= Ω(n)。 对于所有的n≥0，有f(n)=10n2+4n+2>10n2，因此f(n)= Ω(n2)。 由于6*2n+n2>6*2n，所以6*2n+n2= Ω(2n)。 12/4/2018

Omega Notation g(n)仅是f(n)的一个下限。为了使语句f(n)= Ω(g(n))更有实际意义，其中的g(n)应足够地大。 因此常用的是3n+3=Ω(n)及6*2n+n2= Ω(2n)，而不是3n+3=Ω(1)及6*2n+n2= Ω(1)，尽管后者也是正确的。 12/4/2018

有用的结论 定理2-3 如果f(n)=amnm+…+a1n+a0且am>0，则f(n)= Ω(nm)。 12/4/2018

Theta Notation Θ符号适用于同一个函数g 既可以作为f 的上限也可以作为f 的下限的情形。 定义 f(n)= Θ(g(n))当且仅当存在正常数c1,c2 和某个n0，使得对于所有的n≥n0,有 c1g(n)≤f (n)≤c2g(n)。 12/4/2018

例子 3n+2= Θ(n) 10n2+4n+2= Θ(n2) 6*2n+n2= Θ(2n) 12/4/2018

有用的结论 定理2-5 如果f(n)=amnm+…+a1n+a0且am>0，则f(n)= Θ(nm)。 12/4/2018

Little Oh 小写o符号 定义 f(n)=o(g(n))当且仅当f(n) = O(g(n))且f(n)≠Ω (g(n))。 12/4/2018

例子 因为3n+2=O(n2)且3n+2≠Ω(n2)，所以3n+2=o(n2) 。 12/4/2018

一些常用的有关O，Ω和Θ的标记 12/4/2018

关于和与积的有用的引用规则 12/4/2018

Complexity Analysis Examples 矩阵运算 折半搜索(Binary search) 排列、插入排序 12/4/2018

递推求和 12/4/2018

递归求和 12/4/2018

矩阵加法 12/4/2018

矩阵转置 12/4/2018

顺序搜索 tSequentialSearch(n)=Ω (1) tSequentialSearch(n)=Ω (n) 12/4/2018

排列 假定m=n-1。 当k=m时，所需要的时间为Θ(n)。 当k<m时，将执行else语句，此时，for循环将被执行m-k+1次。由于每次循环所花费的时间为Θ(tPerm(k+1,m))，因此，当k<m时，tPerm(k,m)= Θ((m-k+1)tPerm(k+1,m))。使用置换的方法，可以得到： tPerm(0,m)= Θ((m+1)*(m+1)!)= Θ(n*n!),其中n≥1。 12/4/2018

折半搜索 搜索过程从x 与数组[left:right]中间元素的比较开始。 如果x等于中间元素，则查找过程结束。 如果x小于中间元素，则仅需要查找数组的左半部分，所以right 被修改为middle - 1。 如果x大于中间元素，则仅需要在数组的右半部分进行查找，left 将被修改为middle + 1。 12/4/2018

[05 13 19 21 37 56 64 75 80 88 92] [05 13 19 21 37] 56 64 75 80 88 92 05 13 19 [21 37] 56 64 75 80 88 92 查找K=21的过程（查找成功） 12/4/2018

[05 13 19 21 37 56 64 75 80 88 92] 05 13 19 21 37 56 [64 75 80 88 92] 05 13 19 21 37 56 64 75 80 [88 92] 05 13 19 21 37 56 64 75 80] [88 92 查找K=85的过程（查找失败） 12/4/2018

折半搜索 template<class T> int BinarySearch(T a[], const T& x, int n) {// 在a[0] <= a[1] <= ... <= a[n-1 ]中搜索x // 如果找到，则返回所在位置，否则返回- 1 int left = 0; int right = n-1 ; while (left <= right) { int middle = (left + right)/2; if (x == a[middle]) return middle; if (x > a[middle]) left = middle + 1; else right = middle-1 ; } return -1; // 未找到x 12/4/2018

折半搜索性能 While的每次循环(最后一次除外)都将以减半的比例缩小搜索的范围，所以该循环在最坏情况下需执行Θ(logn)次。 12/4/2018

2.5 Practical Complexities 可以利用复杂性函数对两个执行相同任务的程序P和Q进行比较。 假定程序P具有复杂性Θ(n)，程序Q具有复杂性Θ(n2)，可以断定，对于“足够大”的n，程序P比程序Q快。 12/4/2018

函数的值 12/4/2018

函数曲线 12/4/2018

建议 从图中可以看出，随着n的增长，2n的增长极快。事实上，如果程序需要2n执行步，那么当n=40时，执行步数将大约为1.1*1012。在一台每秒执行1000000000步的计算机中，该程序大约需要执行18.3分钟；如果n=50，同样的程序在该台机器上将需要执行13天，当n=60时，需要执行310.56年；当n=100时，则需要执行4*1013年。因此可以认定，具有指数复杂性的程序仅适合于小的n(典型地取n≤40)。 12/4/2018

建议 具有高次多项式复杂性的函数也必须限制使用。 例如，如果程序需要n10执行步，那么当n=10时，每秒执行1000000000步的计算机需要10秒钟；当n=100时，需要3171年；n=1000时，将需要3.17*1013年。 如果程序的复杂性是n3，则当n=1000时，需要执行1秒；n=10000时，需要110.67分钟；n=100000时，需要11.57天。 12/4/2018

2.6 Performance Measurement 性能测量主要关注得到一个程序实际需要的空间和时间。 12/4/2018

设计测试数据 对于许多程序，可以手工或用计算机来产生能导致最好和最坏复杂性的测试数据。 然而，对于平均的复杂性，通常很难设计相应的数据。 当不能给出能产生预期的复杂性的测试数据时，可以根据一些随机产生的测试数据所测量出的最小（最大，平均）时间来估计程序的最坏（最好，平均）复杂性。 12/4/2018

算法的后期测试 在算法中的某些部位插装时间函数 time ( ) 测定算法完成某一功能所花费时间 12/4/2018

程序2-1 顺序搜索(Sequenial Search) template<class T> int SequentialSearch(T a[], const T& x, int n) {//在未排序的数组a[0:n-1]中搜索x，如果找到，则返回所在位置，否则返回- 1 int i; for (i = 0; i < n && a[i] != x; i++); if (i == n) return -1 ; return i; } 12/4/2018

插装 time( ) 的计时程序 double start, stop; time (&start); int k = SequentialSearch(a,n,x); time (&stop); double runTime = stop - start; cout << " " << n << " " << runTime << endl; 12/4/2018

第二章总结 空间复杂性 时间复杂性 顺序搜索/折半搜索算法 名次排序/选择排序/冒泡排序/插入排序算法 矩阵运算 渐进符号（O、Θ 、Ω） 12/4/2018

作业-提问 Page 79-80 15.矩阵乘 16. 12/4/2018

作业 使用 O 分析比较名次排序、选择排序、冒泡排序、插入排序最好和最坏情况下的时间复杂性。列表说明。 12/4/2018