数据结构课件第一章幻灯片.ppt

* 数据结构的三个方面的含义之： 一个算法必须满足以下五个准则： （3）可（能）行性--- 算法的每一步操作都必须是可行的，即每步操作均能在有限时间内完成。 （4）输入数据--- 一个算法有n（n=0)个初始数据的输入。 （5）输出数据--- 一个算法有一个或多个的有效信息的输出。 思考：算法与程序有何区别？ -----数据结构的概念 第一章 绪论 * 数据结构的三个方面的含义之： 算法的描述和实现 描述---可采用自然语言、数学语言或约定的符号语言。 实现---必须借助程序设计语言提供的数据类型及其运算。 本课的描述---采用类C语言 （P9-13 §1.3）。 -----数据结构的概念 第一章 绪论 * 算法的简单分析： 算法设计的要求：正确性、可读性、健壮性、高效率、低存储量需求 算法的效率指算法的执行时间，也称作算法的时间复杂度 算法的存储量需求指算法执行过程中所需的最大存储空间，也称作算法的空间复杂度 -----数据结构的概念 第一章 绪论 * 算法的简单分析： 程序正确性的四个层面： （1）不含语法错误 （2）程序对于n组输入数据能够得出满足规格说明要求的结果。 （3）程序对于精心选择的典型、边界性的n组输入数据能得出满足规格说明要求的结果。 （4）程序对于一切合适的输入数据都能得出满足规格说明要求的结果（穷举）。 -----数据结构的概念 第一章 绪论 返回 * 算法的简单分析之： --------算法效率的度量 1.程序运行所耗费的时间(由下列因素决定)： 算法所选用的策略 问题的规模 书写程序所采用的语言 编译程序所产生的机器代码的质量 机器执行指令的速度 一个算法耗费的时间=算法中每条语句的执行时间之和。 若不考虑机器硬、软件因素，可以认为算法“运行工作量”的大小是问题规模的函数。 -----数据结构的概念 第一章 绪论 * 算法的简单分析之： --------算法效率的度量 2.问题的规模（size)--- 算法求解问题的输入量（或初始数据量）。 3.不考虑机器软硬件环境时算法的时间耗费： 设：执行每条语句所需时间为单位时间，则： 一个算法耗费的时间=所有语句的频度之和。 时间复杂度T(n)--- 即：时间耗费，它是算法求解问题n的函数。 渐近时间复杂度(Asymptotic Time Complexity)--- 即当问题的规模n→∞时的时间复杂度T(n)的数量级（阶），记作：T(n)=O(f(n)) 评价一个算法的时间性能，主要标准是算法的渐近时间复杂度 -----数据结构的概念 第一章 绪论 * 算法效率的度量：采用时间复杂度 例1.5 分析以下程序段的时间复杂度 for (i=1;in;i++) { y=y+1; for (j=0; j=(2*n); j++) x++; } /* 1 * / /* 2 * / * 分析：语句的频度指的是该语句重复执行的次数。一个算法中所有语句的频度之和构成了该算法的运行时间。 语句1的频度是：n-1 语句2的频度是： 则该程序段的时间复杂度： T(n)= * 例1.6 分析以下程序段的时间复杂度 i=1; while (i=n) i=i*2 语句1的频度是：1 设语句2的频度是f(n)，则有： 即 ，取最大值 则该程序段的时间复杂度为： /* 1 * / /* 2 * / * 例1.7 x=1; for (i=1;i=n;i++) for (j=1;j=i;j++) for (k=1;k=j;k++) x++; 由于内循环的执行次数虽与规模n无直接关系，但与外循环的变量取值有关。因此从内层向外层循环分析执行次数。 * * * * 即: T(n)=[n(n+1)(2n+1)/6+n(n+1)/2]/2 所以： T(n)=O(n3/6+低次项) 取T(n)的数量级阶，得最后结果为： T(n)=O(n3) 当n→∞时，即