《数据结构》课件(C语言)-第01章.pptVIP

第*页 ●算法效率的度量 5、算法的描述和算法分析 定义：某算法执行时间T(n)是O(f(n))，意指存在正的常数M和n0，使对于一切n n0，T(n)≤ Mf(n)都成立。如果一个程序的时间复杂度是O(f(n))，就说该程序的运行时间增加率的一个上界为f(n)，或说T(n)是f(n)的大O函数。 例7：设T(n)=n2+4n，则有f(n)=n2，即有： n2 + 4n = O(n2). 因为存在M=2，n0=4，使对于一切nn0，恒有 n2 +4n≤2 n2 第*页 5、算法的描述和算法分析 大O运算规则 规则一 对于任何的常数k和任何的函数f，恒有kf(n)=O(f(n))，即大O忽略常数因子。 规则二 若f(n)=O(g(n))且g(n)=O(h(n))，则f(n)=O(h(n))，即大O的概念是传递的。 规则三 若定义max{f(n)，g(n)}为f(n)与g(n)两者中增长率较快的函数，则有f(n)+g(n)=O(max{f(n),g(n)}). 规则四 若f1(n)=O(g1(n))且f2(n)=O(g2(n))，则f1(n)?f2(n)=O(g1(n) ? g2(n))，即大O符合乘法规则。 有关数学问题：?/?型不定式极限 有关数学定理：罗比塔法则 第*页 例8 求时间函数8nlog(n)+4n3/2的大O. (1) log(n)=O(n1/2) 定义 (2) nlog(n)=O(n?n1/2)= O(n3/2) 规则四 (3) 8nlog(n)=8O(n3/2)= O(n3/2) 规则一 (4) 4n3/2=O(n3/2) 规则一 (5) 8nlog(n)+ 4n3/2 =O(max{8nlog(n)， 4n3/2}） 规则三 max{8nlog(n)， 4n3/2} = max{O(n3/2) ， O(n3/2) }= O(n3/2) 8nlog(n)+ 4n3/2= O(O(n3/2)) 所以有 = O(n3/2) 规则二 8nlog(n)+ 4n3/2= O(n3/2). 5、算法的描述和算法分析 第*页 ●存储空间需求 5、算法的描述和算法分析 算法所需存储空间的度量——空间复杂度（性） 算法的空间复杂度S(n)就是一个算法或程序所需要的存储单元数。 一个非递归程序，并且不含有动态数据结构，在它还未开始执行前，所需存储单元总数即已确定。为简化计算，在算法的空间复杂度分析中，将忽略程序中所有的简单变量和程序的执行代码本身所占的内存空间，而只统计与问题大小有关的数组等结构变量所需的内存量，有时当一些数据、结构变量要占用相当可观的常数量单元时，也可进行统计。 含有动态数据结构的程序应统计内存分配过程的次数乘以该过程产生的动态变量所占单元的大小。递归调用情况较复杂，所需内存单元数等于递归调用的最大深度乘以该递归过程本身所需的内存量，后者包括简单变量、参数变量、调用时系统所需的辅助内存量等。 第*页 第一章 小结 基本内容 *数据和数据结构等名词和术语的确定含义 *抽象数据类型（ADT） *描述算法的类C语言 *从时间和空间角度分析算法的方法 学习要点 *熟悉各名词、术语的含义，掌握基本概念，特别是数据的逻辑结构和存储结构之间的关系 *了解怎样以ADT的角度来描述数据结构 *熟悉类C语言的书写规范 *理解算法五要素 *掌握计算语句频度和估算算法时间复杂度的方法 第*页 第一章 小结 算法设计的基本步骤 明确需求 构造数学模型 设计算法 正确性验证 算法效率的分析 算法的实现 程序的测试与排错 编写文档资料 第一章 绪论 围绕台 * 第一章 绪论 围绕台 * 第一章 绪论 围绕台 * 第一章 绪论 围绕台 * 逻辑结构定义了数据的逻辑关系，物理结构是逻辑结构的具体实现。由于物理存储结构不同导致算法处理不同，但是仍然是实现逻辑结构中定义的内容。 第