算法效率的度量.ppt

算法效率的度量时间复杂度计算时间复杂度计算时间复杂度计算时间复杂度计算时间复杂度分析时间复杂度分析空间复杂度本章的重点是了解数据结构的逻辑结构、存储结构、数据的运算三方面的概念及相互关系，难点是算法复杂度的分析方法。需要达到<领会>层次的内容有：
算法、算法的时间复杂度和空间复杂度、最坏的和平均时间复杂度等概念，算法描述和算法分析的方法、对一般的算法要能分析出时间复杂度。数据结构习题一◆数据类型：◆存储结构：1.2试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。那么我们怎样把这个表中的数据存储到计算机里呢?用高级语言如何表示各结点之间的关系呢?是用一片连续的内存单元来存放这些记录(如用数组表示)还是随机存放各结点数据再用指针进行链接呢?这就是存储结构的问题。1.3常用的存储表示方法有哪几种?◆链接存储方法：1.4设三个函数f,g,h分别为

f(n)=100n3+n2+1000,g(n)=25n3+5000n2,h(n)=n1.5+5000nlgn

请判断下列关系是否成立：

(1)f(n)=O(g(n))(2)g(n)=O(f(n))(3)h(n)=O(n1.5)(4)h(n)=O(nlgn)渐近时间复杂度的表示法的严格定义:
“若T(n)和f(n)是定义在正整数集合上的两个函数，则T(n)=O(f(n))表示存在正的常数C和n0,使得当n≥n0时都满足0≤T(n)≤C·f(n)。”1.5设有两个算法在同一机器上运行，其执行时间分别为100n2和2n,要使前者快于后者，n至少要多大?1.6设n为正整数，利用大"O"记号，将下列程序段的执行时间表示为n的函数。1.7算法的时间复杂度仅与问题的规模相关吗?1.8按增长率由小至大的顺序排列下列各函数：
2100,(2/3)n，(3/2)n，nn,n!，2n，lgn,nlgn,n(3/2),n(1/2)1.9有时为了比较两个同数量级算法的优劣，须突出主项的常数因子，而将低次项用大“O”记号表示。
例如，设T1(n)=1.39nlgn+100n+256=1.39nlgn+O(n),T2(n)=2.0nlgn-2n=2.0lgn+O(n),
这两个式子表示，当n足够大时T1(n)优于T2(n)，因为前者的常数因子小于后者。请用此方法表示下列函数，并指出当n足够大时，哪一个较优，哪一个较劣?