Chapter 2 Program performance

Two Basic Measurement for Program performance 1) Time complexity: The time complexity of an algorithm in terms of number of basic steps. 2) Space complexity The amount of memory an algorithm needed to run to completion

Time Complexity Time complexity of an algorithm in terms of number of basic steps. Choose a basic operation and find a function of the number of the operation need in terms of the size of problem. comparison operation in sorting, + in sum Worst and expected time complexity

Space complexity The amount of memory an algorithm needed to run to completion. the memory for data storage, e.g. for matrix-multiplication with n*n elements, O(n2 ) space complexity The memory for storing programmer The extra memory for the temple memory needed when a program runs

Asymptotic Notation 渐进表示方法 表示随着n的增大，算法执行的时间的增长率和f(n)的增长率相同，称渐近时间复杂度。 T(n)=O(f(n)) 渐进符号（O）的定义：当且仅当存在一个正的常数 C和n0 ，使得对所有的 n  n0 ，有 T(n)  Cf(n)，则 T(n) = O(f(n)) 表示随着n的增大，算法执行的时间的增长率和f(n)的增长率相同，称渐近时间复杂度。 07:34

Definition[Big Oh] f(n) = O(g(n)) iff positive constrain c and n0 exist such that f(n)  c(g(n)) for all n, nn0 . F(n)=3n+2, 3n+2<3n+n=4n, f(n)=O(n) Definition[Omega] f(n) = (g(n)) iff positive constrain c and n0 exist such that f(n)  c(g(n)) for all n, nn0 . F(n)=3n+2 >3n, f(n)= (n)

Definition [Theta] f(n) = (g(n))(read as “f of n is theta of g of n”) iff positive constrains c1 and c2 and n0 exist such that c1 g(n)  f(n)  c2 g(n) for all n, n n0 .f(n) = 3n+2 = (n) Little Oh (o) Definition f(n) = o(g(n)) iff f(n) = O(g(n)) and f(n)  (g(n)) f(n) = nlogn, f(n) =o(n2 ), nlogn =O(n2 ), nlogn  (n2 )

算法分析中对这些函数的使用 (g): functions that grow at least as fast as g，下界函数,和算法无关，由问题本身决定的。 (g) is the set of functions f, such that f(n)  c g(n) for all n  n0, f(n) = 2n,n2, g(n) = n, O(g): functions that grow no faster as g 上界函数，由算法决定的 g(n) = n2, f(n) = nlogn, , n, n2, (g): functions that grow at the same rate as g 精确界函数，若设计的算法复杂性为(g)，称该算法为最佳算法。 (g) = O(g)  (g)

山东大学计算机科学与技术学院 数据结构 第2章 程序性能 空间复杂性 空间复杂性（Space complexity） 是指运行完一个程序所需要的内存大小。 程序所需要的空间构成 : 指令空间（ Instruction space ） 数据空间（ Data space ） 环境栈空间（ Environment stack space） 山东大学计算机科学与技术学院 数据结构 第2章 程序性能

山东大学计算机科学与技术学院 数据结构 第2章 程序性能 空间复杂性组成—指令空间 指令空间 指令空间是指用来存储经过编译之后的程序指令所需的空间。 程序所需要的指令空间的数量取决于如下因素： 把程序编译成机器代码的编译器。 编译时实际采用的编译器选项 目标计算机。 P32 图2-1 不同的编译器将产生不同的程序代码 山东大学计算机科学与技术学院 数据结构 第2章 程序性能

山东大学计算机科学与技术学院 数据结构 第2章 程序性能 空间复杂性组成—数据空间 数据空间 数据空间是指用来存储所有常量和所有变量值所需的空间。 简单变量和常量: 需要的空间取决于所使用的计算机和编译器以及变量与常量的数目。 复合（结构）变量： 包括数据结构所需的空间及动态分配的空间。所需的空间应是每个成员所占用的空间之和。 char 1 float 4 short 2 double 8 int 2 long double 10 long 4 pointer 2 Unit: 字节 图 2-2 Borland C++中简单变量占用空间（p33） 山东大学计算机科学与技术学院 数据结构 第2章 程序性能

山东大学计算机科学与技术学院 数据结构 第2章 程序性能 空间复杂性组成—环境栈 环境栈： 环境栈用来保存函数调用返回时恢复运行所需要的信息。 每当一个函数被调用时，下面的数据将被保存在环境栈中： 返回地址。 函数被调用时所有局部变量的值以及传值形式参数的值（仅对于递归函数而言）。 所有引用参数及常量引用参数的定义。 山东大学计算机科学与技术学院 数据结构 第2章 程序性能

山东大学计算机科学与技术学院 数据结构 第2章 程序性能 空间复杂性组成小结 S(p)=c+Sp(实例特征 ) c: 固定部分，它独立于实例的特征。 包含指令空间（即代码空间）、简单变量及定长复合变量所占用空间、常量所占用空间等等。 Sp(实例特征 ): 可变部分 实例特征 :这些特征包含决定问题规模的那些因素（如，输入和输出的数量或相关数的大小） 包括：复合变量所需的空间,这些变量的大小依赖于所解决的具体问题;动态分配的空间,这种空间一般都依赖于实例的特征）;递归栈空间（递归函数所需要的栈空间）. 递归栈空间主要依赖于 局部变量及形式参数所需要的空间。 递归的深度（即嵌套递归调用的最大层次）。 山东大学计算机科学与技术学院 数据结构 第2章 程序性能

Worst-case time complexity Let Dn be the set of inputs of size n for the problem under consideration, and let I be an element of Dn. Let t(I) be the number of basic operations performed by the algorithm on input I. We define the function W by W(n) = max{t(I) | I  Dn} called the worst-case complexity of the algorithm. W(n) is the maximum number of basic operations performed by the algorithm on any input of size n. .

Average Complexity Let Pr(I) be the probability that input I occurs. Then the average behavior of the algorithm is defined as A(n) = I  Dn Pr(I) t(I). We determine t(I) by analyzing the algorithm, but Pr(I) cannot be computed analytically.

算法时间复杂性分析 理论分析 （非常困难，被普遍认可） 实验比较 (往往不被认可，因为算法的执行时间往往是输入数据的函数） 确定算法的基本计算是什么 基于循环体，递归公式求解，算法的性质分析、利用级数和积分等求解基本计算数量函数f(n) 实验比较 (往往不被认可，因为算法的执行时间往往是输入数据的函数） 在testbed 上用 finish time  end time

山东大学计算机科学与技术学院 数据结构 第2章 程序性能 常用的渐进符号标记（P61） 山东大学计算机科学与技术学院 数据结构 第2章 程序性能

理论分析 1) 对级数可以采用积分的方法求解 2) 多项式采用最高次幂 3）数学手册（如前面的表） 4）根据算法进行结构化分析 ik 定理 2.1 3）数学手册（如前面的表） 4）根据算法进行结构化分析

问题按时间复杂性分类 多项式时间算法（容易被计算） O(1)，常数时间算法，swap(a,b) O(n) 线性算法, sum(list[],n) 指数时间算法，如O(2n ),当n>50,几乎无法计算。NP-hard problems

实际测试 利用系统的时钟 在程序开始基本运算前加上语句 在基本运算结束时，加上 Start = clock() Finish = clock() 实际运行时间= finish-start

实际可计算 109 instructions/second Teraflop computer the 32yr time becomes approx 10 days.

109 instructions/second

The examples for time complexity analysis Matrix multiplication Sorting searching

多项式求值算法 把 * 作为基本操作, T(n)=O(n)

Complexity computation Theoretical analysis Define the basic operations and find the number of basic operations needed in the worst (expected ) case Set up a test bed for data, and then measure the real running time needed of a program on the test data

c[i][j]=c[i][j]+a[i][k]*b[k][j]; } 例1：N×N矩阵相乘 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]=c[i][j]+a[i][k]*b[k][j]; } 算法中的基本操作 * c[i][j]=c[i][j]+a[i][k]*b[k][j]; 07:34

山东大学计算机科学与技术学院 数据结构 第2章 程序性能 例2-9 计算名次 元素在队列中的名次（rank）可定义为队列中所有比它小的元素数目加上在它左边出现的与它相同的元素数目。 例如，给定一个数组a=[4, 3, 9, 3, 7]作为队列，则各元素的名次为r =[2, 0, 4, 1, 3]。 //对处于位置i的元素，计算位于1-(i-1)位置上比自己小的元素个数。同时也对这些元素的rank贡献。 template <class T> void Rank(T a[], int n, int r[]) { 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] + + ; } 比较次数 : 1+2+3+…+n-1 =(n-1)*n/2 山东大学计算机科学与技术学院 数据结构 第2章 程序性能

排序算法 对给定的无序对象序列和一个全序关系>, 输出一个按升序（降序）的新序列。 插入排序 冒泡排序 快速排序

插入排序 思想：初始假定已排序数组长度为1，只有a[0].然后从目前序列的最后面j向前看，只要比 t大，把A的元素向后移动一位，直到a[j] <t,把t插入位置j+1。 程序：//a[0,n-1] template <class T> void InsertionSort(T a[], int n) { for ( int i=1; i<n; i++ ) { T t=a[i]; int j; for ( j=i-1; j>=0 && t<a[j]; j-- ) a[j+1] = a[i] a[j+1]=t; } 2019/2/24

最坏情况 找个特例，即原来是降序序列，该增序序列 分析： 最好情况 比较 n-1次，移动0次 最坏情况 找个特例，即原来是降序序列，该增序序列 比较 (n-1)+(n-2)+…+1=n*(n-1)/2次，移动也是n*(n-1)/2次 2019/2/24

之五：冒泡排序 思想：从下向上，把“轻”的元素上浮。自下(a[0])而上(a[n-1])依次两两比较，发现逆序即进行交换直至a[n-1]，下一次再从a[0]至a[n-2]做如上处理，如此进行n-1遍或当某遍未发生交换即可结束。 程序： template <class T> void Bubble(T a[], int n) //一次冒泡 { for ( int i=1; i<n-1; i++ ) if ( a[i]>a[i+1]) Swap(a[i],a[i+1]); } template <class T> // 截至到位置i的冒泡 void BubbleSort(T a[], int n) { for ( int i=n; i>1; i-- ) Bubble(a, i); //从位置i 开始冒泡 2019/2/24

最坏情况 比较 (n-1)+(n-2)+…+1=n*(n-1)/2次，交换也是n*(n-1)/2次 分析： 最好情况 比较 n-1次，交换0次 最坏情况 比较 (n-1)+(n-2)+…+1=n*(n-1)/2次，交换也是n*(n-1)/2次 本章介绍的几种排序方法的时间复杂性都是O(n*n)的，后面还会陆续介绍性能更好的方法 2019/2/24

奇偶排序

快速排序Quicksort Input: A set of numbers S. Output: The elements of S sorted in increasing order. 1.若 |S| < 3 直接比较排序；返回 2选S中最左元素作为pivot元素y. 3.分割S为S1,S2, S1={x|x<y}; S2={x|x>y}. 4.递归调用RandQS对S1,S2排序； 5 输出RandQS(S1); y; RandQS(S2);

把S分为S1,S2的过程。 左找大，右找小，右放vac, 左放刚空出的右元素, 当l>r, vac为pivot的 位置. 45 14 62 51 75 96 33 84 20 45 14 20 51 75 96 33 84 62 45 14 20 33 75 96 51 84 62 33 14 20 45 75 96 51 84 62 33 14 20 45 75 96 51 84 62 33 14 20 51 62 75 84 96 14 20 33 45 51 62 75 84 96

QuickSort 最坏时间复杂性O(n2 )—已经排序序列 期望时间复杂性O(nlogn),比其他排序算法节省一半以上的时间。

山东大学计算机科学与技术学院 数据结构 第14章 分而治之算法 快速排序实现 template<class T> void QuickSort(T*a, int n) {// 对a[0:n-1] 进行快速排序; 要求a[n] 必须有最大关键值 quickSort(a, 0, n-1); void quickSort(T a[], int l, int r) {//排序a[l:r]，a[r+1]有大关键值 if (l>=r) return; int i=l, // 从左至右的游标 j=r+1; // 从右到左的游标 T pivot=a[l]; 山东大学计算机科学与技术学院 数据结构 第14章 分而治之算法 37

山东大学计算机科学与技术学院 数据结构 第14章 分而治之算法 // 把左侧>= pivot的元素与右侧<= pivot 的元素进行交换 while (true) { do {// 在左侧寻找>= pivot 的元素 i=i+1; } while (a[i]< pivot); do {// 在右侧寻找<= pivot 的元素 j=j-1; } while (a[j]>pivot); if (i>=j) break; // 未发现交换对象 Swap(a[i], a[j]); } //设置pivot a[l]=a[j]; a[j] = pivot; quickSort(a, l, j-1); // 对左段排序 quickSort(a, j+1, r); // 对右段排序 山东大学计算机科学与技术学院 数据结构 第14章 分而治之算法 38

两种搜索（查找）算法介绍 顺序搜索 性能： 不成功查找比较次数=n-1; template <class T> int SequentialSearch(T a[], const T &x, int n) { int i; for ( i=0; i<n && a[i]!=x; i++ ) //数组下标从0~(n-1) if ( i==n) return -1; return i; } 性能： 不成功查找比较次数=n-1; 成功查找比较次数=1*p0,+2*p1,+…+n*pn-1，其中pi为第i 个元素被查找的概率； 一般认为pi均等，为1/n，则=(1+n)/2 2019/2/24

折半搜索//前提序列是有序的（增或减） 思想：对给定的表a[0..n] 和将被搜索元素x，首先将x与a中间元素a[n/2]比较，相等则返回;否则，若x比中间元素小,则只在a[0..n/2-1]继续搜索;否则在a[n/2+1,n-1]继续搜索。 2019/2/24

template <class T> int BinarySearch(T a[], const T &x, int n) { int left=1; int right=n-1; while (left<=right) { int middle=(left+right)/2; // int 强制把商变成整数 if ( x==a[middle]) return middle; //找到 if ( x>a[middle]) left=middle+1; // 确定下一步从左右哪半块继续找 else right=middle-1; } return -1; 性能： 最好情况一次比较成功； 最多经过┌log n ┐次比较即可得出结论; 2019/2/24

山东大学计算机科学与技术学院 数据结构 第2章 程序性能 复杂性函数的取值变化 logn n nlogn n2 n3 2n 1 2 3 4 5 8 16 32 24 64 160 256 1024 512 4096 32768 65536 4294967296 山东大学计算机科学与技术学院 数据结构 第2章 程序性能

山东大学计算机科学与技术学院 数据结构 第2章 程序性能 实际复杂性 山东大学计算机科学与技术学院 数据结构 第2章 程序性能

exercise P97, 28