(2)--第1章 绪论-算法数据结构.ppt

《(2)--第1章 绪论-算法数据结构.ppt》由会员分享，可在线阅读，更多相关《(2)--第1章 绪论-算法数据结构.ppt（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、-算法第1章 绪论n n算法定义算法定义n n算法特征算法特征n n算法的描述算法的描述n n算法评价算法评价1.4 1.4 算法和算法分析算法和算法分析n n算法定义：算法定义：一个有穷的指令集一个有穷的指令集，这些指令为解决某，这些指令为解决某一特定任务规定了一个运算序列一特定任务规定了一个运算序列算法定义算法定义n n算法的描述：算法的描述：uu自然语言自然语言uu 流程图流程图uu 程序设计语言程序设计语言uu 伪码伪码算法描述算法描述uu 输入输入 有有0 0个或多个输入个或多个输入uu 输出输出 有一个或多个输出有一个或多个输出(处理结果处理结果)uu 确定性确定性 每步定义都是确

2、切、无歧义的每步定义都是确切、无歧义的uu 有穷性有穷性 算法应在执行有穷步后结束算法应在执行有穷步后结束uu 有效性有效性 每一条运算应足够基本每一条运算应足够基本算法的特性算法的特性算法的评价算法的评价uu正确性uu可读性uu健壮性uu高效性（时间代价和空间代价）算法的效率的度量算法的效率的度量算法效率：用依据该算法编制的程序在计算机上执行所消耗的时间来度量事后统计事前分析估计1.1.事后统计：事后统计：利用计算机内的计时功能，不同算法利用计算机内的计时功能，不同算法的程序可以用一组或多组相同的统计数据区分的程序可以用一组或多组相同的统计数据区分 缺点：缺点：必须先运行依据算法编制的程序必

3、须先运行依据算法编制的程序所得时间统计量依赖于硬件、软件等环境因素，所得时间统计量依赖于硬件、软件等环境因素，掩盖算法本身的优劣掩盖算法本身的优劣 2.2.事前分析估计：事前分析估计：一个高级语言程序在计算机上运行所消耗的时间取一个高级语言程序在计算机上运行所消耗的时间取决于：决于：依据的算法选用何种策略依据的算法选用何种策略 问题的规模问题的规模 程序语言程序语言 编译程序产生机器代码质量编译程序产生机器代码质量 机器执行指令速度机器执行指令速度 时间复杂度的渐进表示法时间复杂度的渐进表示法算法中基本语句重复执行的次数是问题规模n的某个函数f(n),算法的时间量度记作：T(n)=O(f(n)

4、表示随着n的增大，算法执行的时间的增长率和f(n)的增长率相同，称渐近时间复杂度。数学符号“O”的定义为：若T(n)和f(n)是定义在正整数集合上的两个函数，则T(n)=O(f(n)表示存在正的常数C和n0，使得当nn0时都满足0T(n)Cf(n)。n*n阶矩阵加法：阶矩阵加法：for(i=0;i n;i+)for(j=0;j n;j+)cij=aij+bij;语句的频度语句的频度（Frequency Count):重复执行的次数：重复执行的次数：n*n;T(n)=O(n 2)即：矩阵加法的运算量和问题的规模即：矩阵加法的运算量和问题的规模n的平方是同一个量级的平方是同一个量级分析算法时间复杂

5、度的基本方法分析算法时间复杂度的基本方法找出语句频度最大的那条语句作为基本语句计算基本语句的频度得到问题规模n的某个函数f(n)取其数量级用符号“O”表示例例1 1x=0;y=0;for(int k=0;k n;k+)x+;for(int i=0;i n;i+)for(int j=0;j n;j+)y+;f(n)=n2T(n)=O(n2)例例2 2时间复杂度是由时间复杂度是由嵌套最深层嵌套最深层语句的频度决定的语句的频度决定的 void exam(float x ,int m,int n)float sum ;for(int i=0;i m;i+)sumi=0.0;for(int j=0;j

6、n;j+)sumi+=xij;for(i=0;i m;i+)cout i “:”sum i endl;f(n)=m*nT(n)=O(m*n)总结总结若若f(n)=amnm+am-1nm-1+a1n+a0是是m次次多项式，则多项式，则T(n)=O(nm)。忽略所有低次幂项和最高次幂系数，体现出增长率的含义例例3 3分析以下程序段的时间复杂度分析以下程序段的时间复杂度i=1;while(i=n)i=i*2;即即f(n)log2n，取最大值取最大值f(n)=log2n所以该程序段的时间复杂度所以该程序段的时间复杂度T(n)=T(n)=O(logO(log2 2n)n)下列程序段的时间复杂度是（）【2

7、014研究生统考】count=0;for(k=1;k=n;k*=2)for(j=1;j=n;j+)count+;O(log2n)O(n)O(nlog2n)O(n2)ABCD提交单选题2分例例4 4有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同顺序顺序查找，在数组查找，在数组aiai中查找值等于中查找值等于e e的元素，返的元素，返回其所在位置。回其所在位置。for(i=0;i n;i+)for(i=0;i n;i+)if(ai=e)return i+1;if(ai=e)return i+1;return 0;return 0;最好情况：最好情况：1 1次次 最坏情况：最

8、坏情况：n n平均时间复杂度为平均时间复杂度为:O(n):O(n)时间复杂度时间复杂度T(n)T(n)按数量级递增顺序为：按数量级递增顺序为：复杂度高复杂度高复杂度低复杂度低当当n n取得很大时，指数时间取得很大时，指数时间算法和多项式时间算法在算法和多项式时间算法在所需时间上非常悬殊所需时间上非常悬殊千万次运算大约千万次运算大约1S，O(n2)的算法当的算法当n=10000时时有可能超过有可能超过1S。渐进空间复杂度渐进空间复杂度空间复杂度空间复杂度:算法所需存储空间的度量，记作算法所需存储空间的度量，记作:S(n)=O(f(n)S(n)=O(f(n)其中其中n n为问题的规模为问题的规模(

9、或大小或大小)n算法要占据的空间算法要占据的空间算法本身要占据的空间，输入算法本身要占据的空间，输入/输出，指令，输出，指令，常数，变量等常数，变量等算法要使用的算法要使用的辅助空间辅助空间原地原地工作工作若输入数据所占空间只取决于问题本身，和算法无关，则只需要分析除输入和程序之外的额外空间。额外空间相对于输入数据量来说是常数,则称此算法为原地工作.建议大家建议大家-三个三个“一定要一定要”一定要一定要将算法理解透彻、明确数据数据结构后，再写程序将算法理解透彻、明确数据数据结构后，再写程序1一定要一定要学会调试程序的方法学会调试程序的方法 3设断点设断点F10 F10 减少测试的数据量减少测试

10、的数据量明确算法思想的每一步明确算法思想的每一步确定逻辑结构、然后确定存储结构确定逻辑结构、然后确定存储结构一定要一定要掌握编译错误修改的技巧掌握编译错误修改的技巧2修改一个编译错误后重新编译修改一个编译错误后重新编译先注释掉一部分代码先注释掉一部分代码不要急于求成不要急于求成 1C+C+语法规则不熟练（指针、结构体、函数的定义和调用）语法规则不熟练（指针、结构体、函数的定义和调用）根据任务逐一编写、编译、调试各个功能模块，不该将所有根据任务逐一编写、编译、调试各个功能模块，不该将所有代码写完再编译调试代码写完再编译调试建议不要只读不写不要只读不写3先明确算法思想，多动手多思考，不耻下问先明确算法思想，多动手多思考，不耻下问不要好高骛远不要好高骛远2写程序时依次考虑算法的正确性、可读性、健壮性、高写程序时依次考虑算法的正确性、可读性、健壮性、高效性效性建议大家建议大家-三个三个“一定不要一定不要”