《数据结构域算法设计.jlmao-算法设计与分析-ch-算法概述》由会员分享，可在线阅读，更多相关《数据结构域算法设计.jlmao-算法设计与分析-ch-算法概述（67页珍藏版）》请在金锄头文库上搜索。
1、算法设计与分析算法设计与分析毛剑琳毛剑琳 Department of AutomationDepartment of Automation km_km_关于这门课关于这门课n n 为什么要学习这门课？为什么要学习这门课？ uu无论是计算机理论还是应用，算法都是非常重要的。算法无论是计算机理论还是应用，算法都是非常重要的。算法 可以认为是思想和思路，从更广泛的意义来看，算法是一可以认为是思想和思路，从更广泛的意义来看，算法是一 种解决问题的技术。种解决问题的技术。 uu提高学生们的问题求解能力，算法这门课可以告诉学生如提高学生们的问题求解能力，算法这门课可以告诉学生如 何应用一些特定的策略来解决
2、问题。何应用一些特定的策略来解决问题。n n 学习方法学习方法 uu掌握思想，边学边练掌握思想，边学边练复杂网络系统研究学科方向团队申请Page 2第一章第一章 算法概述算法概述本章要点本章要点 理解算法的概念。理解算法的概念。 理解什么是程序，程序与算法的区别和内在联系。理解什么是程序，程序与算法的区别和内在联系。 掌握算法的计算复杂性概念。掌握算法的计算复杂性概念。 掌握算法渐近复杂性的数学表述。掌握算法渐近复杂性的数学表述。 掌握用掌握用C+C+语言描述算法的方法。语言描述算法的方法。复杂网络系统研究学科方向团队申请Page 4Kunming University of Science
3、(2) 算法的复杂程度很重要，决定计算花费的时间，以及空间。算法的复杂性算法的复杂性n n 算法的复杂性用算法所消耗的资源来评判算法的复杂性用算法所消耗的资源来评判 uu所消耗资源越多，复杂性就越高所消耗资源越多，复杂性就越高 uu这个指标反映算法的效率。这个指标反映算法的效率。 n n 计算机资源：计算机资源： uu时间资源：需要时间资源的量时间资源：需要时间资源的量 uu空间资源：需要空间资源的量空间资源：需要空间资源的量n n 复杂性与复杂性与3 3个量有关：个量有关： uuNN：问题规模：问题规模 uuI I：输入：输入 uuA A：算法：算法复杂网络系统研究学科方向团队申请Page
4、11算法复杂性分析算法复杂性分析 n n 算法复杂性算法复杂性 = = 算法所需要的计算机资源算法所需要的计算机资源n n 算法的时间复杂性算法的时间复杂性T T( (n n) )；n n 算法的空间复杂性算法的空间复杂性S S( (n n) )。n n 其中其中n n是问题的规模（输入大小）。是问题的规模（输入大小）。复杂网络系统研究学科方向团队申请Page 12算法渐近复杂性分析中常用函数算法渐近复杂性分析中常用函数n n （1 1）单调函数）单调函数n n 单调递增：单调递增：mm n n f f( (mm) ) f f( (n n) ) ; ;n n 单调递减：单调递减：mm n n
5、f f( (mm) ) f f( (n n););n n 严格单调递增：严格单调递增：mm ) f f( (n n).).n n （2 2）取整函数）取整函数n n x x ：不大于：不大于x x的最大整数；的最大整数；n n x x ：不小于：不小于x x的最小整数。的最小整数。 取整函数的若干性质取整函数的若干性质n n x x-1 00，有：，有：n n n n/ /a a / /b b = = n n/ /abab ; ;n n n n/ /a a / /b b = = n n/ /ab ab ; ; n n a a/ /b b ( (a a+(+(b b-1)/-1)/b b; ;n
6、 n a a/ /b b ( (a a-(-(b b-1)/-1)/b b; ;n n f f( (x x)= )= x x , , g g( (x x)= )= x x 为为单调递增函数。单调递增函数。n n（3 3）多项式函数）多项式函数n n p p( (n n)= )= a a0 0+a a1 1n n+a a2 2n n2 2+a ad dn nd d； a ad d0;0;n n p p( (n n) = ) = ( (n nd d););n n f f( (n n) = ) = OO( (n nk k) ) f f( (n n) )多项式有界；多项式有界；n n f f( (n
7、n) = ) = OO(1) (1) f f( (n n) ) c c; ;n n k k d d p p( (n n) = ) = OO( (n nk k) ;) ;n n k k d d p p( (n n) = ) = ( (n nk k) ;) ;n n k k d d p p( (n n) = ) = o o( (n nk k) ;) ;n n k k 0:0:n n a a0 0=1;=1;n n a a1 1=a a ; ;n n a a-1-1=1/=1/a a ; ;n n ( (a amm) )n n = = a amn mn ; ;n n ( (a amm) )n n =
8、 = ( (a an n) )m m ; ;n n a amma an n =a am+n m+n ; ;n n a a1 1 a an n为为单调递增函数单调递增函数; ;n n a a1 1 n nb b= = o o( (a an n) )n n e ex x 1+ 1+x x; ;n n |x| |x| 1 1 1+ 1+x x e ex x 1+ 1+x+xx+x2 2 ; ;n n e ex x= 1+= 1+x+ x+ ( (x x2 2), as ), as x x0;0;n n（5 5）对数函数）对数函数n n log log n n = log= log2 2n n; ;n
9、 n lg lg n n = log= log1010n n; ;n n ln ln n n = log= loge en n; ;n n loglogk kn n = (log = (log n n) )k kl; l;n n log log log log n n = log(log = log(log n n););n n for a0,b0,c0 for a0,b0,c0n n |x| |x| 1 1 n n for for x x -1, -1,n n for any for any a a 0, , 0, , log logb bn n = = o o( (n na a) )n n
10、（6 6）阶层函数）阶层函数n n Stirlings approximationStirlings approximation 算法分析中常见的复杂性函数算法分析中常见的复杂性函数我们关注的是这些函数的增长次数我们关注的是这些函数的增长次数nlog2nnnlog2nn2n32nn!103.3103.3*101021031033.6*1061026.61026.6*1021041061.3*10309.3*101571031010310*103106109104131041.3*1051081012105171051.7*10610101015106201062*10710121018复杂网络
11、系统研究学科方向团队申请Page 24说明: (1)大规模数据才能区分算法的高效和低效。 （2）数量级对于算法分析来说，具有深远意义。对数函数增长最慢。算法的时间复杂性算法的时间复杂性n n （1 1）最坏情况最坏情况下的时间复杂性下的时间复杂性T Tmaxmax( (n n) = max ) = max T T(I) | size(I)=(I) | size(I)=n n n n （2 2）最好情况最好情况下的时间复杂性下的时间复杂性T Tminmin( (n n) = min ) = min T T(I) | size(I)=(I) | size(I)=n n n n （3 3）平均情况平
12、均情况下的时间复杂性下的时间复杂性T Tavgavg( (n n) =) =其中其中I I是问题的规模为是问题的规模为n n的实例，的实例，p p(I)(I)是实是实 例例I I出现的概率。出现的概率。算法的最优、最差和平均效率算法的最优、最差和平均效率n n 算法规模是衡量算法效率的一个方面，另一方面，算法规模是衡量算法效率的一个方面，另一方面， 算法的输入也对算法效率有所影响。算法的输入也对算法效率有所影响。 n n 以顺序查找算法为例，以顺序查找算法为例，复杂网络系统研究学科方向团队申请Page 26SequentialSearch (A0, n-1, K) /功能: 用顺序查找在给定的
13、数组中查找给定的值 /输入: 数组A0, n-1和查找键K /输出: 返回第一个匹配K的元素的下标; 如果没有，则返回-1i 0 While i00，存在正数存在正数和和n n0 0 00使得对所有使得对所有n n n n0 0有：有：0 0 f f( (n n)00，存在正数存在正数和和n n0 0 00使得对所有使得对所有n n n n0 0有：有：0 0 cgcg( (n n) ) b. b.渐近分析记号的若干性质渐近分析记号的若干性质n n （1 1）传递性：）传递性：n n f f( (n n)= )= ( (g g( (n n)， g g( (n n)= )= ( (h h( (n
14、 n) ) f f( (n n)= )= ( (h h( (n n)；n n f f( (n n)= )= OO( (g g( (n n)， g g( (n n)= )= OO( (h h( (n n) ) f f( (n n)= )= OO( (h h( (n n)；n n f f( (n n)= )= ( (g g( (n n)， g g( (n n)= )= ( (h h( (n n) ) f f( (n n)= )= ( (h h( (n n)；n n f f( (n n)= )= o o( (g g( (n n)， g g( (n n)= )= o o( (h h( (n n) ) f f( (n n)= )= o o( (h h( (n n)；n n f f( (n n)= )= ( (g g( (n n)， g g( (n n)= )= ( (h h( (n n) ) f f( (n n)=
