算法性能分析(长安大学课件)

1、算法性能算法性能-高效率与低存储量需求高效率与低存储量需求通常，效率指的是算法执行时间；存储量指的是算法执行过程中所需的最大存储空间，两者都与问题的规模有关。算法效率的衡量方法和准则算法效率的衡量方法和准则通常有两种两种衡量算法效率的方法: 事后统计法事后统计法事前分析估算法事前分析估算法缺点：缺点：1必须执行程序 2其它因素掩盖算法本质和算法执行时间时间相关的因素因素：1 1算法算法选用的策略的策略2 2问题的规模问题的规模3 3编写程序的语言语言4 4编译编译程序产生的机器代码的质量的质量5 5计算机计算机执行指令的速度的速度 一个特定算法的算法的“运行工作量运行工作量”的大小，只依赖于问

2、题的规模（通常用整数量n表示），或者说，它是问题规模的函数是问题规模的函数。 假如，随着问题规模 n 的增长，算法执行时间的增长率和算法执行时间的增长率和 f(n) 的增长的增长率相同率相同，则可记作：T (n) = O(f(n)称称T (n) 为算法的为算法的(渐近)时间复杂度。时间复杂度。 以下六种计算算法时间的多项式是最常用以下六种计算算法时间的多项式是最常用的，其关系为：的，其关系为： O(1)O(n)O(n)O(nn)O(n2)O(n3)l 指数时间的关系为：指数时间的关系为： O(2n)O(n!)O(nn) 当当n取得很大时，指数时间算法和多项式时取得很大时，指数时间算法和多项式时

3、间算法在所需时间上非常悬殊。因此，只要有间算法在所需时间上非常悬殊。因此，只要有人能将现有指数时间算法中的任何一个算法化人能将现有指数时间算法中的任何一个算法化简为多项式时间算法，那就取得了一个伟大的简为多项式时间算法，那就取得了一个伟大的成就。成就。如何估算如何估算 算法的时间复杂度？算法的时间复杂度？算法算法 = = 控制结构控制结构 + + 原操作原操作 （固有数据类型的操作）算法的执行时间算法的执行时间 =原操作原操作(i)(i)的执行次数的执行次数原操作原操作(i)(i)的执行时间的执行时间 算法的执行时间算法的执行时间 与与 原操作执行次数之和原操作执行次数之和 成正比成正比 从算

4、法中选取一种对于所研究的问题来说是 基本操作基本操作 的原操作，以该基本操作 在算法中重复执行的次数在算法中重复执行的次数 作为算法运行时间的衡量准则。 一般地，常用一般地，常用最深层循环内最深层循环内的语句的语句中的原操作的中的原操作的执行频度执行频度( (重复执行的次数重复执行的次数) )来表示。来表示。例例一一两两个个矩矩阵阵相相乘乘void mult(int a, int b, int& c ) / 以二维数组存储矩阵元素，c 为 a 和 b 的乘积 for (i=1; i=n; +i) for (j=1; j=n; +j) ci,j = 0; for (k=1; k=n; +

5、k) ci,j += ai,k*bk,j; /for /mult基本操作: 乘法乘法操作时间复杂度: O(n3)例例二二选选择择排排序序 void select_sort(int& a, int n) / 将将 a 中整数序列重新排列成自小至大有序的整数序列中整数序列重新排列成自小至大有序的整数序列。 / select_sort基本操作: 比较比较(数据元素)操作操作时间复杂度: O(n2)j = i; / 选择第选择第 i i 个最小元素个最小元素for ( k = i+1; k n; +k ) if (ak aj ) j = k;for ( i = 0; i1 & chan

6、ge; -i) / bubble_sort基本操作: 赋值赋值操作时间复杂度: O(n2) change = FALSE; / change 为元素进行交换标志 for (j=0; j aj+1) aj aj+1; change = TRUE ; / 一趟起泡四、算法的存储空间需求四、算法的存储空间需求算法的空间复杂度定义为空间复杂度定义为: : 表示随着问题规模表示随着问题规模 n 的增大，的增大，算法运行所需存储量的增长率算法运行所需存储量的增长率与与 g(n) 的增长率相同。的增长率相同。S(n) = O(g(n)算法的存储量算法的存储量包括:1输入数据输入数据所占空间2程序本身程序本身所占空间3辅助变量辅助变量所占空间 若输入数据输入数据所占空间只取决于问题 本身，和算法无关和算法无关，则只需要