《数据结构和算法课件2算法和复杂度》由会员分享，可在线阅读，更多相关《数据结构和算法课件2算法和复杂度（22页珍藏版）》请在金锄头文库上搜索。
1、数据结构与算法数据结构与算法For For 软件学院软件学院0808级本科生级本科生 2009-20102009-2010秋秋1.4-1.6 1.4-1.6 算法和复杂度算法和复杂度算法: 是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。一个算法通常具有五个重要特性: 有穷性 有穷步结束 确定性 唯一执行路径 可行性 可以通过基本运算实现 输入 零个或多个输入 输出 一个或多个输出非数学有穷性！算法和算法复杂度2算法和复杂度算法和数据结构是两个不可分割的统一体程序 = 数据结构 + 算法数据结构通过算法实现操作算法根据数据结构设计程序3算法和复杂度算法设计
2、的要求: 正确性 正确反映需求(通过测试) 可读性 有助于理解、调试和维护 健壮性 完备的异常和出错处理 高效率与低存储的需求 时间、空间的要求4算法和复杂度算法效率的衡量方法1事后统计利用计算机内记时功能。缺点：必须先运行依据算法编制的程序；所得时间统计量依赖于硬件、软件等环境因素，掩盖算法本身的优劣5算法和复杂度算法效率的衡量方法2事前分析估计一个高级语言程序在计算机上运行所消耗的时间取决于：依据的算法选用何种策略问题的规模程序语言编译程序产生机器代码质量机器执行指令速度时间复杂度和空间复杂度6算法和复杂度算法的时间度量从算法中选取一种对于研究的问题来说是基本操作的原操作，以该基本操作重复
3、执行的次数作为算法执行的时间度量。例，for ( j = 1 ；j=n ；j+ )X = X + 1 ；for ( i = 1 ；i=n ；i+ )(c)for ( i = 1 ；i 时的时间复杂性，被称之为渐进时间复杂度。空间复杂度：算法的所需的空间和问题规模的函数。记为 S(n)。当 n- 时的时间复杂性，被称之为渐进空间复杂度。8算法和复杂度给定两个正值函数 f 和 g，考虑以下定义： 定义1： 如 果 存 在 正 数 c和 N， 对 于 所 有 的 nN， 有f(n)cg(n), 则f(n)=O(g(n)。 上述定义表明，如果对于足够大的n，或大于某自然数N的n，存在正数c，使 f 不
4、大于cg，则 f 是g的大O符号。大大O O符号符号9算法和复杂度例如： f(n)=2n2+3n+1=O(n2)在这里，g(n)=n2，c和N的可选值如表所示：表 对于函数f(n)=2n2+3n+1=O(n2)，根据大O定义计算得到的c和N的不同值 N 1 2 3 4 5 c 6 大O符号10算法和复杂度算法分析中常见的复杂度O(1) O(lgn) O(n) O(nlgn) O(n2) O(n3) O(2n) O(n!) O(nn)常数 对数 多项式 指数复杂度举例11算法和复杂度Time to FinishInput Size (n)O(nx)O(n)O(1)O( lg n)O(an)复杂度
5、举例12算法和复杂度算法的重要性：算法的重要性：计算机不是万能的，并非所有的算法，计算机都能够计算出有用的结果。差的算法不一计算机不是万能的，并非所有的算法，计算机都能够计算出有用的结果。差的算法不一 定有实际意义。定有实际意义。 举一个例子加以说明。举一个例子加以说明。假定时间复杂性函数的时间单位为假定时间复杂性函数的时间单位为 us。函数函数 n=20 n=50 n=100 n=500 1000n .02s .05s .15s .5s1000nlogn .09s .3s .6s 4.5s 100n2 .04s .25s 1s 25s10n3 .02s 1s 10s 21分分nlogn .4
6、s 1.1小时小时 220天天 5 108世纪世纪2n/3 .0001s 0.1s 2.7小时小时 5 108世纪世纪2n 1s 35年年 3 104世纪世纪3n 58分分 2109世纪世纪易性算法易性算法顽性算法顽性算法在大多数的情况下，我们只对时间复杂度感兴趣，它通常计算程序执行过程中赋值和比较操作的次数。 例1： for (i=sum=0; in; i+) Sum +=a i; 赋值2+2n次，渐近复杂度O(n)。确定渐近复杂度14算法和复杂度确定渐近复杂度例2： for ( i = 0; i n; i+ ) for ( j = 1, sum=a 0; j = i; j+ ) sum +
7、=a j; cout“sum for subarray 0 through” i “is”sumendl; 15算法和复杂度符号符号符号如果存在正数c1,c2及N，对于所有的nN，有c1g(n)f(n) c2g(n), 则f(n)= (g(n)。 16算法和复杂度最好、平均和最坏情况有时，算法中基本操作重复执行的次数随问题的输入不同而不同。例，顺序查找算法Status serch ( int a ，int n ，int e )for ( i = 0 ；i =n - 1 ；+i )if ( e = ai ) return TRUE ；比较次数的复杂度是多少？return FALSE ；17算法和
8、复杂度最好、平均和最坏情况最好情况：算法需要的最少步骤最坏情况：算法需要的最多步骤平均复杂度：将处理每个输入所执行的步骤数与该输入出现的概率相乘，然后将所有相乘的结果相加。18算法和复杂度最好、平均和最坏情况有时，算法中基本操作重复执行的次数随问题的输入不同而不同。例，顺序查找算法Status serch ( int a ，int n ，int e )for ( i = 0 ；i =n - 1 ；+i )if ( e = ai ) return TRUE ；最好 1 次比较，最坏 n 次比较，平均 (n+1)/2 次比较。return FALSE ；19算法和复杂度数据结构的选择分析问题分析问题在算法设计之前初步设计数据结构在算法设计之前初步设计数据结构注意可扩展性注意可扩展性比较时空开销的优劣比较时空开销的优劣20算法和复杂度小结和后续内容算法特性算法特性算法复杂度分析算法复杂度分析渐进复杂度渐进复杂度最好、最坏、平均时间复杂度最好、最坏、平均时间复杂度后续内容：线性表后续内容：线性表21算法和复杂度作业和后续内容作业作业复习复习C+相关内容，准备上机相关内容，准备上机预习、复习教材预习、复习教材熟悉熟悉SSD5网站上的第一部分内容网站上的第一部分内容后续内容后续内容线性表线性表课件上传公共邮箱课件上传公共邮箱: Email: 密密 码码: ssdut0822算法和复杂度
