2014/4/7 812算法描迷分析 /类的实现部分 Complex::Complex(double realVal,double imagVal){ ◆ 算法 realpart=realVal; ◆重要性：数据的运算是通过算法描述的 imagpart=imagVal; 定义：非形式地说，算法是任意一个良定义的计 void Complex::assign(Complex&z)( 算过程，它以一个或多个值作为输入，并产生 realpart =z.realpart; 个或多个值作为输出。因此，一个算法就是一系 imagpart=z.imagpart; 列将输入转换为输出的计算步骤。 Complex add(Complex&z1,Complex&z2)( ”5要素 Complex sum(z1片 粮入、输出、有穷性（有穷步骤，每步时间有限） sum.realpart +=z2.realpart; 、捧哥凝老卖的柔限次所有 执行路径) sum.imagpart+=z2.imagpart: return sum; ◆ 算法与程序的联系与区别 S1.2算法描迷分析 S1.2算法描述分析 输入实例 ■算法分析 一个问题的输入实例是由满足问题陈述中的限制、 并能计算出该问题解的所有输入构成的。 算法效率的度量 。事后统计：利用计算机内部的计时功能 算法描述 缺陷 自然语言、数学语言、伪语言、程序语言等均可 ,必须先运行依据算法编制的程序 本课程以C为主，但不拘泥于细节 时间统计量依赖于计算机的软硬件环境 double start,stop; 算法评价 time (&start); 正确性、可读性、健壮性、 时空性能 main process(n,…月 time(&stop): double runTime stop-start; printf ("%d%dIn",n,runTime ) s1.2算法描迷与分折 81.2算法描述分析 ◆ 算法分析 算法的时间是每语句执行时间的总和 。事前分析估算（时间） 每语句的执行时间=该语句执行次数（频度） 求出该算法的一个时间界限函数 一些影响因素： X该语句执行1次的时间 算法的策略 假定：每语句执行1次的时间为1个时间单位 问题的规模 则：算法的执行时间=Σ各语句频度 书写程序的语言 问题的规模(Size)n 编译器产生的机器代码的质量 机器执行指令的速度 输入量的大小，如 时间复杂度：算法的运行时间，是问题规模的函数2014/4/7 5 // 类的实现部分 Complex::Complex(double realVal, double imagVal){ realpart = realVal; imagpart= imagVal; } void Complex::assign(Complex& z){ realpart = z.realpart; imagpart= z imagpart; 25 imagpart= z.imagpart; } Complex add(Complex& z1, Complex& z2){ Complex sum(z1); sum.realpart += z2.realpart； sum.imagpart += z2.imagpart； return sum; } §1.2 算法描述 分析  算法  重要性：数据的运算是通过算法描述的  定义：非形式地说，算法是任意一个良定义的计 算过程，它以一个或多个值作为输入，并产生一 个或多个值作为输出。因此，一个算法就是一系 列将输入转换为输出的计算步骤 26 。  5要素 输入、输出、有穷性（有穷步骤，每步时间有限） 确定性（算法只有唯一执行路径）、可行性（所有 操作可通过已经实现的基本运算有限次实现之）  算法与程序的联系与区别 §1.2 算法描述 分析  输入实例 一个问题的输入实例是由满足问题陈述中的限制、 并能计算出该问题解的所有输入构成的。  算法描述 自然语言、数学语言、伪语言、程序语言等均可 27 自然语言、数学语言、伪语言、程序语言等均可 本课程以C为主，但不拘泥于细节  算法评价 正确性、可读性、健壮性、 时空性能  算法分析 算法效率的度量 事后统计：利用计算机内部的计时功能 缺陷 必须先运行依据算法编制的程序 §1.2 算法描述 分析 28 必须先运行依据算法编制的程序 时间统计量依赖于计算机的软硬件环境 double start, stop; time (&start); main process(n, …); time (&stop); double runTime = stop -start; printf ("%d%d\n" , n, runTime ); 事前分析估算(时间) 求出该算法的一个时间界限函数 一些影响因素:  算法的策略 §1.2 算法描述 分析 29 算法的策略 问题的规模 书写程序的语言 编译器产生的机器代码的质量 机器执行指令的速度 §1.2 算法描述与分析  算法分析 算法的时间是每语句执行时间的总和 每语句的执行时间=该语句执行次数（频度） X该语句执行1次的时间 假定：每语句执行1次的时间为1个时间单位 30 假定 每语句执行 次的时间为 则：算法的执行时间=∑各语句频度  问题的规模（Size）n 输入量的大小，如…  时间复杂度：算法的运行时间，是问题规模的函数