1、 第 二 章算 法 分 析 基 础算法分析的 任务 :对设计出的每一个具体的算法 ,利用数学工具，讨论其复杂度。上节 下节2.1 算法分析体系及计量对 算法的评价 有两个大的方面：一是人对算法的维护的方便性。二是算法在实现运行时占有的机器资源的多少即算法的运行的时间和空间效率。上节 下节2.1.1 算法分析的评价体系人对算法的维护主要有编写、调试、改正和功能扩充等工作 ,这就需要在算法设计时注重算法的可读性 。为了算法的利用率 ,也要考虑算法的 适用范围 ,注重算法的 通用性 、 可重用性 和 可扩充性 。机器对算法的运行效率主要包括时间效率和空间效率。算法在完成功能的前题下最好是占用空间少而
2、且执行时间短。另外在算法实现时 ,要考虑算法在运行过程中与使用者进行交互的情况。这就要求 ,算法的交互部分要具有 友好性 和 健壮性 。上节 下节总之，对 算法的分析和评价 ，一般应考虑正确性、可维护性、可读性、运算量及占用存储空间等诸多因素。其中评价算法的三条主要 标准 是：(1) 算法实现所耗费的 时间 ；(2) 算法实现所所耗费的存储 空间 ，其中主要考虑辅助存储空间；(3) 算法应易于 理解 ，易于编码，易于调试等等。上节 下节1.和算法执行时间相关的因素 ： 1）问题中数据存储的数据结构2）算法采用的数学模型 3） 算法设计的策略4）问题的规模 5）实现算法的程序设计语言 6）编译算
3、法产生的机器代码的质量 7）计算机执行指令的速度 上节 下节2.1.2 算法的时间复杂性2算法效率的衡量方法通常有两种 衡量算法效率 的方法 : 1）事后统计法（有缺点，较少使用）2）事前分析估算法 算法的时间效率是问题规模的函数。假如 ,随着问题规模 n的增长 ,算法执行时间的增长率和 f(n)的增长率相同 ,则可记作 :T(n)=(f(n) ,称 T(n)为算法的 渐近时间复杂度(Asymptotic Time Complexity),简称 时间复杂度 。 是数量级的符号。上节 下节3时间复杂度估算因为：算法 =控制结构 +原操作 (固有数据类型的操作 )所以：算法的执行时间 = 原操作的
4、执行次数 *原操作语句的频度 指的是该语句重复执行的次数。一个算法转换为算法后所耗费的时间 ,除了与所用的计算软、硬件环境有关外，主要取决于算法中指令重复执行的次数，即语句的频度相关。上节 下节一个算法中 所有语句的频度之和 构成了该算法的运行时间。例如： for(j=1;j=n;+j) for(k=1;k=n;+k)+x；语句 “ +x、 k=n、 +k” 的频度是 n2，语句 “ j=1、 k=1” 的频度是 1，语句 “ j=n;+j” 的频度是 n。算法运行时间为： 3*n2+2n+2。上节 下节对较复杂的算法计算算法的运行时间 ,经常从算法中选取一种对于所研究的问题来说是 基本 (或者说是主要 ) 的原操作 ,以该基本操作在算法中重复执行的次数作为算法运行时间的衡量准则。这个原操作 ,多数情况下是最深层次循环体内的语句中的原操作。例如： for(i=1;i=n;+i)for(j=1;j=n;+j) ci,j=0;for(k=0;k=n;+k)ci,j= ci,j+ai,k*bk,j;该算法的基本操作是乘法操作 ,时间复杂度为 n3 。上节 下节
