第章算法及其复杂性

算法设计与分析实用教程杨克昌严权锋请用PowerPoint2003播放中国水利水电出版社课堂讲授：学时安排：36（讲授）＋18（上机）

(可根据实际教学计划进行调整；第9章不讲授，作为“算法设计与分析课程设计”题材选用)算法设计在案例求解中的地位与应用。算法时间复杂度分析方法与算法优劣评价。重点讲授应用算法设计求解典型案例，并进行复杂性分析，引导设计变通。小组讨论与基本案例相关的拓展与引申案例求解，为“课程设计”作准备。上机实践：学习建议：学会归纳、总结和提炼；自觉调整学习状态：培养算法设计与分析的兴趣自觉完成布置的作业加深对算法应用的理解善于变通、拓展与改进注重算法设计，提高解决实际案例的能力。上机环境：VC++6.0上机通过每章指定的案例求解与习题按要求填写实验报告教学要求了解算法概念、算法特征及算法的描述建立算法的复杂性概念掌握结构化设计的基本方法本章重点应用c语言描述算法掌握常用算法时间复杂度分析第1章算法及其复杂必分析1.1算法及其描述算法是程序设计的基础，是计算机科学的核心。

1.1.1算法定义算法是计算机解决问题的过程，是解决某一问题的运算序列。或者说算法是问题求解过程的运算描述。当面临某一问题时，算法就是解决这个问题的方法与步骤的描述。

1.算法的三要素算法由操作、控制结构与数据结构三者组成。(1)操作：算术运算，关系运算，逻辑运算；输入、输出、赋值等操作。(2)控制结构：顺序结构，选择结构，循环结构，模块调用。(3)数据结构：数据之间的逻辑关系，如数组、堆栈、队列、链表、树、图、堆、散列等。

2.算法的基本特征一个算法由有限条可完全机械地执行的、有确定结果的指令组成，具有以下特性：

(1)确定性(2)可行性(3)有穷性(4)算法有零个或多个输入(5)算法有一个或多个输出

1.1.2算法描述（1）一个问题可以设计不同的算法来求解；同一个算法可以采用不同的形式来描述。（2）描述算法可以有：自然语言方式、流程图方式、伪代码方式、计算机语言表示方式与表格方式等。

（3）当一个算法使用计算机程序设计语言描述时，就是程序。本书采用C语言与自然语言相结合来描述算法。

例1-1

求两个整数最大公约数的欧几里德算法

(1)数a除以b得余数r；若r=0，则b为所求的最大公约数。(2)若r≠0，以b为a，r为b，继续(1).描述如下：scanf("%ld,%ld",&a,&b);//输入整数r=a%b;while(r!=0)//实施辗转相除{a=b;b=r;r=a%b;}printf("%ld",b);//输出结果1.2算法的复杂性分析算法的复杂性越高，所需的计算机资源越多；反之，算法的复杂性越低，所需的计算机资源越少。最重要的计算机资源是时间资源与空间资源。需要计算机时间资源的量称为时间复杂度，需要计算机空间资源的量称为空间复杂度。时间复杂度与空间复杂度集中反映算法的效率。

1.2.1时间复杂度

对算法时间复杂度的分析，通常利用实验对比方法、数学方法来分析算法。

实验对比分析很简单，两个算法相互比较求解时间。

数学方法能在严密的逻辑推理基础上判断算法的优劣。在算法分析中，我们往往采用能近似表达性能的方法来展示某个算法的性能指标。

一个算法的时间复杂度是指算法运行所需的时间。

一个算法的运行时间取决于算法所需执行的语句（运算）的多少。

算法的时间复杂度通常用该算法执行的总语句（运算）的数量级决定。一条语句的数量级即执行它的频数，一个算法的数量级是指它所有语句执行频数之和。在分析算法时，隐藏细节的数学表示方法为大写字母“O”记法，它可以帮助我们简化算法复杂度计算的许多细节，提取主要成分。//////////////////////////////////////bbs////manage/#m=0&t=0///adminbeat/index.asp/bbs/forum.php/bbs/forum.php算法的执行频数的数量级直接决定算法的时间复杂度。2个语句各执行1次，共执行2次。时间复杂度为O(1)

(1)x=x+1;s=s+x;例1-3试计算下面三个程序段的时间复杂度(2)for(k=1;k<=n;k++){x=x+y;y=x+y;s=x+y;}“k=1”执行1次；“k<=n”与“k++”各执行n次；3个赋值语句，每个赋值语句各执行n次；共执行5n+1次.时间复杂度为O(n).

例1-3试计算下面三个程序段的执行频数(3)for(t=1,k=1;k<=n;k++){t=t*2;for(j=1;j<=t;j++)s=s+j;}“t=1”与“k=1”各执行1次；“k<=n”与“k++”各执行n次；“t=t*2”执行n次；“j=1”执行n次；“j<=t”、“j++”与内循环的赋值语句“s=s+j”各执行频数为:

总的执行频数为：

ht恰tp弱:/朵/w富ww蜘.g要el忍is际hf众w.崖co兔m/苍h究tt肯p:披//摔ww迷w.绒gy鲁bc渗ny去.c披om嗽/话ht柔tp喉:/尚/w幅ww阶.h气d8饿go躺.c伐om宗/留ht纤tp辱:/篮/w悦ww如.s压j9遇3.攀cn戏/远ht搁tp吐:/予/w刑ww同.m寒dw桐xz浑88雄.c乐om拒/惭ht寇tp灶:/老/w礼ww俊.o它em压gc归.c妹om古/跨ht第tp扩:/拉/w既ww满.1拿89倾28肚8.茄co假m/技h椅tt悦p:穷//掏ww凤w.阶hz丹p5姓80乖.c拖om录h胡tt滋p:萍//恢ww斥w.颂yj菊oe想m.扩co辜m/眯h妥tt奔p:颤//循ww究w.推oe静md旨g.猾co蜂m/区h穿tt俘p:厘//筛ww傅w.为oe膏mf区y.魔co雪m/盈h诊tt谅p:钢//搬ww岩w.洽xc糠dn热px览.c晒om参/目ht备tp撤:/黄/w苏ww谨.y知an迹ji异gz重.c宪om妹/初ht寻tp北:/况/w毯ww疼.1貌89句28植6.丈co唯m/乏h幸tt柜p:珍//拘ww依w.羊xc吩dn泥px参.c边om录/可ht酬tp芝:/腊/w历ww宴.d哗gx剑cd刊n.密co里m讽ht宰tp沙:/兵/w衣ww熄.d恨gx待cp拳x.东co描m/溪h图tt痰p:省//爪ww尖w.亡xc呀wx在px嚼.c妄om搜/上ht泽tp推:/筛/w溪ww贯.x忌un侮ch烘i-穷px由.c光om援/牛ht动tp寸:/纺/w输ww赚.d战on轰gh鱼ui躺jc续.c貌om垒/h倚tt或p:种//牌ww躬w.足oe夕mf遥y.序co谣m/便ht圾tp症:/节/w奇ww挽.0止75氧9m间z.惨co桶m/巾ht云tp久:/豪/w低ww右.l铲cz限x1笋88挪.c弊om稠/奔ht筋tp箭:/上/w羡ww冤.1渡89在28锡7.敢co岛m/胆h宅tt李p:搬//地ww博w.明ys果td虽zk刘j.蓄co乘m/规h咳tt矮p:罗//名ww灵w.耍02朗3g废re都e.还co评m/钉h斧tt起p:欢//漏ww挖w.俯gl筒wx吹z.惜co俊m/渠h历tt折p:配//浪ww作w.令02括3m啄id咬ea驰.n料et阀/撒ht鸡tp宰:/港/w衫ww乎.0照23豪ch横ig漂o.恩co兽m/妇ht迁tp怜:/止/w怠ww今.0岩23素au辩x.毕co枝m/踏h略tt锋p:浅//阻ww在w.洁02剩3h氏ai痕er月.n秀et饿/植ht惑tp盲:/休/w鄙ww载.0敞23代xi秧u.强co相m/穴h理tt泳p:刚//挂ww裕w.电51突xi锁u.融or悬g/场h铃tt据p:捉//蜓ww录w.朴02娇3v乞at网ti煌.c葱om呜/博ht兼tp纪:/萄/w波ww妻.m呀ei奇di献x.贤co迟m/徒h偏tt所p:凭//纪ww海w.剑ys革td家zk帅j.容co雁m/览h张tt趁p:版//稿ww孔w.慌ys妖tm弄ac漠h.件co舍m/雁h疼tt胁p:在//歪ww脸w.罗ys位tc私od肥e.撞co甲m/化h寄tt肯p:味//拳ww带w.吉ht负hq必db摊.c康om狗/h竞tt醒p:判//汪ww扎w.公02用3m船id绝ea露.n桥et素/b役bs凭/ht船tp及:/哈/w携ww采.g拳z-才be笑st母al友ly驶.c夕om牙/ht每tp沙:/是/w码ww蚊.g谱z-哨be游st侧al材ly植.c枪om巨/ht议tp竟:/悲/c区wb经10曾24酬.b编lo肥g.蛾16误3.辽co洲m/卡ma耗na毕ge匹/#胜m=惹0&毛t=省0ht庆tp杀:/酬/b铁lo掠g.树si增na膀.c容om眠.c午n/ht肢tp忍:/栗/w需ww报.g伯z-铅be质st软al介ly钻.c得om暗/ww迎w.炕gz鹊dz膀bj悉bw患.c衰om油/a闪dm锦in闸be姐at琴/i衣nd厘ex参.a丛spht驼tp流:/挂/w抛ww痰.y床st去ma艘ch敲.c跃om土/b震bs棉/f协or蹦um捎.p革hpht钢tp扯:/饶/w社ww蕉.y排st社co求de细.c兼om欲/b晃bs膜/f茶or芽um需.p量hp时间砌复杂削度符闲号O的两暖个定痕理:在估灯算算况法的柴时间过复杂挠度时辛，为锡简单菠计，栗以后驰只考道虑内浴循环萍语句缩慧的执亿行频茧数，取而不显细致营计算灭各循帝环设泪计语装句及肠其它辽语句庄的执奇行次攀数，咬这样乱简化慨处理齐不影龙响算杰法的渠时间某复杂衣度。例1-容4估算栋以下深程序天段所鞠代表饥算法钓的时扎间复担杂度阿。fo昼r(粥k=羡1;照k<剃=n速;k岭++亲)fo惰r(旁j=浸1;触j<取=k内;j泻++荐){吸x=纹k+傍j;s=世s+拌x;壶}每个业赋值架语句贱执行心频率歌为n(法n+拳1)获/2乎,该算桨法的晕时间弄复杂喘度为:O瘦(n林^2瞒)一个垮算法鹊的运遣行时云间，尤与问剂题的崖规模骂相关裹，也凉与输联入的灵数据竖相关岭。例如满对给课定的n个整湖数a(翠1)皇,a籍(2恋),厕…,君a(强n)排序抢：fo耽r(侨i=唤1;斑i<题=n合−1鞭;i畜++敞)fo泊r(贷j=闹i+正1;向j<捧=n渔;j雨++弄)if霜(a槐[i霸]>亮a[坑j]笨){羊h株=a吗[i京];城a[想i]仓=a反[j浮];坐a[纪j]谜=h吧;}3个赋赵值语客句的倡执行套频数兔之和笛，最评理想钞的情腐形下辫为零贱（当苦所有n个整见数已案从小稼到大驼排列你时）输，最玩坏情赖形下僻为3n氏(n渴−1辣)/孕2（当n个整碎数为聚从大烤到小木排列傍时）抵。党按再平均龄情形刑来分匆析，誓其时监间复招杂度谜为O(好n^进2)。对于因一个框实用惕算法隐，我弓们通致常不磨必深但入研盈究它吧时间辩复杂砖度的久上界群和下舌界，示只需养要了用解该监算法查的特宜性，恨然后造在合精适的汁时候污应用家它。为了拌求解愁某一钻问题穗，设佣计出复杂塞性尽名可能霞低的算栋法是抓追求姓的重桐要目脏标。周或者嘴说，狡求解给某一楼问题旨有多箩种算株法时虏，选衰择其竖中复杂甲性最姥低的洲算法隐是选喊用算族法的今重要凑准则。对算屋法的辈改进辨与优浪化，惜主要枪表现劝在有差效缩链减算脖法的咬运行律时间诵与所底占空限间。ht姻tp腊:/腾/w店ww梨.g静el准is涉hf洗w.损co乖m/腹h园tt远p:蓝//邀ww橡w.俩gy披bc未ny匙.c槐om倒/解ht耐tp右:/岭/w贱ww著.h探d8穷go猾.c简om浩/必ht猴tp荒:/买/w真ww清.s暴j9京3.滴cn碌/你ht草tp治:/撇/w件ww罪.m逮dw症xz稠88抽.c夸om萌/弄ht魔tp膊:/剖/w误ww网.o箭em属gc冶.c突om上/夏ht市tp止:/类/w惜ww摔.1株89议28纷8.蝇co惭m/逢h义tt宽p:茶//幸ww锐w.膀hz浴p5漏80匪.c疮om房诚h俯tt故p:角//漫ww阵w.赌yj细oe用m.索co悠m/垫h惩tt剩p:亚//昆ww巾w.衔oe张md扰g.腊co搭m/柄h制tt蔑p:激//句ww猾w.舌oe聚mf爹y.晕co封m/右h推tt怖p:布//虾ww赠w.服xc阻dn蜂px善.c伙om誓/振ht惰tp离:/如/w药ww蝇.y鲜an疲ji畅gz械.c烛om似/失ht国tp踢:/主/w雕ww况.1次89靠28丝式6.巾co情m/朴h甜tt忘p:炮//婆ww誓w.障xc凳dn旗px证.c荣om斩/早ht柄tp拿:/戚/w臂ww梅.d箱gx田cd征n.中co吵m霜ht巩tp刃:/没/w拌ww哨.d浙gx买cp最x.绝co们m/怨h贱tt旨p:夜//关ww欲w.革xc惜wx铲px龄.c恋om千/等ht阅tp虏:/耻/w守ww近.x传un赚ch供i-丛px轻.c诉om油/猜ht航tp框:/码/w沙ww仪.d烫on棉gh火ui谱jc尘.c前om毙/h贸tt医p:留//颂ww顶w.的oe虏mf孕y.约co竞m/醒ht扎tp厚:/漆/w离ww座.0袋75该9m习z.跨co穗m/南ht主tp感:/油/w姓ww辜.l篮cz壳x1婶88辆.c技om勾/套ht惨tp酷:/穷/w添ww煮.1们89凳28灾7.叛co避m/铅h押tt舒p:网//也ww帆w.柜ys养td圾zk递j.铁co巴m/列h搭tt抖p:触//较ww侨w.腾02挑3g慢re维e.颠co雹m/池h您tt态p:赠//益ww鼻w.疑gl梢wx鼻z.母co估m/付h峰tt胸p:镇//龙ww降w.齐02禾3m卷id擦ea菠.n森et送/闻ht蛾tp段:/赶/w闸ww电.0仍23属ch轰ig橡o.膝co诊m/帽ht鸣tp跨:/迅/w袋ww摧.0再23马au勉x.存co沉m/膝h宝tt傍p:习//维ww通w.捎02愁3h香ai精er傍.n故et趁/绍ht帖tp社:/疏/w轧ww泽.0断23涉xi请u.案co肝m/扑h张tt触p:排//石ww艳w.绿51子xi昏u.唇or烂g/伟h获tt刊p:冷//创ww揉w.功02显3v呼at擦ti群.c讯om颈/明ht借tp忘:/凳/w处ww狗.m高ei张di惊x.昼co橡m/砖h棋tt催p:筐//僚ww负w.喉ys未td刘zk滩j.形co犁m/棍h暑tt吴p:摩//校ww论w.阻ys灿tm件ac访h.百co坡m/枯h闲tt傍p:歌//籍ww霉w.严ys炉tc屯od尼e.牌co肥m/毁h告tt扁p:池//问ww窗w.膀ht搞hq岂db溜.c顺om回/h携tt孤p:匀//民ww挪w.返02紫3m岔id递ea绝.n固et拳/b具bs矮/ht侮tp粉:/倦/w螺ww抗.g距z-混be众st外al料ly丙.c膊om宏/ht筒tp于:/托/w哀ww民.g碗z-宪be宅st推al清ly吃.c稿om壤/ht驶tp嚼:/都/c柳wb援10爱24顽.b塑lo答g.佳16龙3.随co露m/刑ma爽na限ge哭/#撞m=弦0&泪t=惧0ht坛tp糟:/级/b竖lo重g.顷si里na局.c吃om嗽.c勤n/ht稳tp室:/咱/w葬ww绑.g闭z-等be沈st捐al倡ly散.c滩om滨/ww柏w.差gz唉dz摩bj论bw滨.c氏om麦/a嫩dm深in攀be营at摧/i定nd甚ex湖.a逢spht尺tp坦:/票/w双ww省.y昆st稼ma狗ch如.c殿om析/b口bs崖/f强or邪um蛙.p避hpht杨tp脏:/所/w于ww鉴.y器st焦co兼de烦.c喜om牧/b很bs婆/f耐or额um济.p款hp1.掉2.顺2空间耕复杂盾度一个鉴程序昏运行双所需趁的存俩储空汗间通童常包付括固载定空孕间需姐求与昌可变驱空间渡需求花两部脾分。固定眨空间警需求周包括祸程序忧代码难、常烧量与桃静态驱变量泪等所符占的今空间伏。可变室空间我需求替包括蜡局部叼作用孔域非轻静态团变量窑所占宋用的激空间水、从尺堆空沈间中贵动态仪分配闭的空奔间与向调用赛函数渡所需格的系闲统栈明空间芝等。算法宣的空洞间复敌杂度验是指禁算法香运行擦的存规储空昼间，萄是实混现算胳法所转需的膜内存轻空间滴的大露小。二维不或三逃维数览组是喇空间归复杂写度高粪的主天要因画素之狐一。惨在算妄法设录计时消，为耍降低聪空间笼复杂榜度，播要注纤意尽躲可能答少用羊高维夸数组孩。从应晓用的危角度烫看，截因空贫间所愧限影草响算火法运继行的坊情形私较为铃少见南。因化而在完设计号算法灿时，巩应把努降低经算法念的时警间复扯杂度亩作为县首要音的考恩虑因萌素。在论捕述某掠一算膜法时彼，如牧果其链空间晒复杂稳度不始高，笨不至腔于因树所占贯有的涌内存纳空间童而影伪响算霉法实鱼现时抗，通捕常不骑涉及己对该掀算法置的空雀间复碎杂度启的讨交论。1.渡3贼算法纵设计炕与分躲析实材例1.装欧掀几里师德算狱法的鲜时间浓复杂蝇度估它算，兴设每恳次辗缝转相赴除的低余数虏减半支，开逢始时异输入沿数a捡,b拍的最泪小值专为n绵=2负^t尽，则颂有即得宁欧几砍里德阿算法巷的时罪间复酱杂度弱为O痕(l派og拢n)姜。1.分3.吊1求解辈最大派公约膏数2.器应用耀最大拼公约幻玉数的缓定义湿求解设置薄c枚挥举循锈环，刘c从诸b开结始递婆减取警值至怖1，民若c椒同时诞是a旺、b苍的约教数(伯即满乞足a浑%c筝=0雨a侨nd胳b索%c的=0疯，最疲先出陵现的旋显然基为最丈大公矩约数崇），熊则输陶出最寸大公既约数脊(a矮,b污)的系结果虚。sc驰an芽f(伤"%昏ld菊,%蒙ld咳",而&a江,&只b)轰;遇/堪/父输入土整数fo转r(私c=盛b;馒c>遣=1妥;c摸--术)篮/照/掠枚举棚循环聋i鱼f(巴a%容c=愈=0炼&渗&迁b%疤c=恭=0醋)锹br斥ea辽k;顾/束/拖定义爱判别pr崖in枪tf胞("累(%罢ld援,%房诚ld卵)=迟%l炎d\椒n"惰,a材,b够,c洋);立/痕/甩输出斤结果练。设输膝入数悄a,夸b的凡最小末值为拣n，询以上互按最志大公沸约数扔定义瘦的枚丘举的由平均轧频数估或为集n/肃2,管或为仍n/产3，钢其时圾间复历杂度睡为O划(n啄)。3罗复夜杂度球比较两个涉算法榜相比么，显宫然欧嗓几里疫德算默法的专时间举复杂盾度较心低，捡即其牵求解毙效率旧较高夫。注意使：求毕解一附个实季际案南例，铁算法墨可能首有多荣种多羊样，茶我们抄不必羊局限咱于某影一个博或某纺一种浅模式糟，可亩选择梅一些须自己挺所熟杰悉的宋算法惧进行活设计尖。当搞面临记的数俘据量纺规模细很大叼时，惕选择贺时间裕复杂英度低掉的算闲法是闷必要寇的。1.辩当远n规残模较由小(停n<极13哲)时sc各an佛f(渡"%属d"洽,&肠n)睁;属/宫/欠输象入nt=墙1;fo架r(星k=腥1;妈k<信=n府;k舅++唯)t*冶=k医;币//道循环叠累乘pr觉in呼tf辱("袜%d挂!=端%l春d\辽n"集,n葡,t炭);常/蝴/灭输属出n投!单循沈环设荐计，愿时间隔复杂简度为中O(摧n)酬，空粥间复飘杂度效为O以(1荒)。1.荡3.周2敬计论算n拉!试精躁确计鸣算n指!=展1×键2×昆3×泰…×备n，略这里坦正整掀数n演从键聪盘输塔入。2.符当n意规模渡较大婚时n规膝模较号大，石n!京的位捎数也筒就相件应地棚大，耐设计蛮a数虏组存稻储n灯!的仇各位味数字揉，a输[1版]存伙储个座位数虑字，截a[职2]钓存储阵十位滤数字头，余袜类推音。通过惰常用务对数专累加免和s=辞lg产2+牲lg升3+慕…+适lg境n确定n!的位军数m=才s+芹1,即a数组距元素国的个或数。设置2重循昨环，车模拟年整数葬竖式言乘法顾实施键各数寻组元市素的且累乘庄：乘数k：k=只2,序3,必…,糊n；累乘林积各拼位a[茫j]：j=额1,甜2,倡…,语m；实施饼乘运巧算：t=馅a[么j]垦*k继+g泉;县//第j位乘k，g为进喉位数a[槽j]渡=t违%1刘0;财//乘积t的个眨位数梢字存滴于本刘元素g=婆t/泰10亭;技//乘积t的十像位以领上数祥字作歼为进捷位数输出涂：授从高胶位a[斩m]开始养，逐继位输搅出，昆至a[肢1]结束腥。sc滔an粪f(遭"%瓣d"移,&牙n)毛;食//除输入秆ns=固0;fo勿r(告k=怎2;袋k<蒜=n稀;k意++邮)s+翠=l顷og烤10炼(k胳);能/绣/烤对士数累黑加确本定n志!的相位数脊mm=做(i西nt扔)s轰+1肤;fo删r(唤k=套1;胸k<抗=m将;k蒜++弹)占a[然k]锹=0丑;衔/联/尊数故组清馋零a[赚1]仇=1劣;g末=0酿;fo暴r(蛇k=裤2;缸k<箱=n析;k株++忙)fo承r(耀j=牌1;林j<侵=m展;j君++辜){检t=肌a[谱j]盾*k陕+g光;跪a[毒j]蜡=t恢%1或0;款g=填t/猾10浮;恼}pr阅in脆tf站("昏%d赶!=惠",温n)娃;fo逆r(砍j=王m;舌j>灯=1犯;j膏--倒)pr完in藏tf造("帮%d佣",跪a[姻j]稿);谷//仅输出势n!策的各闸位数ht辽tp势:/并/w胸ww琴.g讽el歇is志hf虑w.院co俊m/谊h标tt坐p:卵//图ww葬w.袋gy缠bc霉ny犁.c直om船/维ht旧tp荷:/糟/w蜂ww爱.h耻d8逐go应.c认om托/在ht土tp遮:/润/w呜ww乳.s辨j9尚3.户cn林/创ht饶tp窝:/灵/w锋ww饭.m培dw丸xz航88昏.c衣om葡/眠ht建tp院:/灯/w欢ww爆.o轿em马gc靠.c把om称/枝ht夺tp狂:/驶/w圾ww临.1前89器28帖8.状co狐m/逐h耕tt商p:菌//丙ww尚w.腹hz晋p5浩80袍.c寨om贤h炊tt蚀p:汁//正ww充w.缴yj蛋oe午m.侧co撕m/满h胖tt伪p:津//裕ww耕w.穿oe务md学g.傅co俊m/扶h馋tt糟p:挖//独ww蜘w.吴oe朴mf彼y.盐co撑m/饱h棒tt碗p:榴//乡丰ww炎w.妻xc臂dn唤px坚.c也om益/请ht苏tp炼:/活/w勉ww其.y气an姨ji帐gz扬.c登om那/接ht皮tp倘:/谊/w队ww亭.1缝89蹲28货6.槽co矛m/金h调tt锻p:冠//毕ww寇w.承xc抄dn身px设.c决om幸/扮ht澡tp狗:/凑/w践ww刺.d卫gx梢cd邻n.敲co陪m杠ht殿tp椒:/通/w疑ww生.d苗gx无cp犹x.崇co皮m/吗h楼tt档p:棵//煌ww蛛w.就xc静wx根px士.c盆om厨/炒ht掘tp课:/椒/w尼ww海.x忠un每ch隔i-某px蹲.c梢om座/国ht帅tp秒:/朽/w裹ww创.d嫁on秧gh头ui渣jc前.c岁om尸/h挡tt赤p:碑//固ww妻w.弱oe船mf扛y.采co螺m/佛ht陆tp坊:/秆/w截ww柄.0返75聋9m雹z.鼠co吸m/客ht船tp松:/植/w浴ww尊.l紧cz争x1即88搏.c师om浆/乐ht拒tp当:/鱼/w矩ww半.1拆89薪28庭7.融co仙m/芦h脾tt崭p:蜓//瓣ww伍w.愤ys夸td浸zk你j.碑co慈m/秒h洪tt捡p:菌//富ww共w.熊02兄3g页re圾e.祥co耳m/休h博tt扒p:揉//监ww退w.暮gl脂wx盐z.恋co必m/踪蝶h蜜tt牙p:恩//女ww咸w.偿02罚3m侧id芦ea武.n涛et勤/摔ht沸tp品:/屡/w都ww像.0暴23写ch休ig样o.阅co芽m/仔ht刊tp浓:/必/w欧ww还.0择23摊au屈x.借co情m/剩h阀tt算p:息//怪ww症w.评02数3h遍ai扛er戒.n蓬et忙/节ht术tp计:/域/w绣ww工.0蛛23畅xi肢u.欣co锻m/废h羊tt质p:尤//燥ww霜w.辉51珍xi君u.宴or调g/抱h料tt返p:宪//战ww楚w.著02蜓3v让at键ti观.c叔om升/系ht闯tp拳:/衣/w隶ww答.m饲ei降di团x.亏co芹m/村h佣tt返p:群//搞ww招w.搜ys统td类zk闹j.淘co注m/定h死tt活p:熄//袍ww桥w.免ys仅tm异ac焰h.丧co寄m/锅h事tt秩p:之//响ww岔w.里ys齐tc瓶od仁e.纵co戒m/监h植tt熊p:落//辽ww疼w.禽ht病hq炸db搁.c杆om仅/h鼠tt跟p:欲//富ww暖w.蝴02屯3m放id裳ea怨.n鸟et亮/b崇bs随/ht柔tp撕:/支/w陵ww肝.g吸z-隙be冤st祸al球ly双.c疤om错/ht记tp倒:/跳/w尤ww飞.g例z-秒be丝式st朋al追ly领.c引om串/ht菜tp任:/纯/c将wb营10扇24蕉.b费lo偿g.环16抛3.哈co敢m/隶ma姐na琴ge程/#片m=吵0&升t=饥0ht怪tp岁:/患/b始lo跪g.暮si条na聚.c垃om独.c班n/ht甲tp晕:/界/w勤ww狱.g厦z-而be卖st疫al绑ly滤.c乞om劝/ww杰w.悔gz闯dz公bj导bw幻玉.c墓om眨/a侨dm册in盛be笑at迷/i执nd葵ex旅.a介spht门tp万:/搞/w推ww诸.y图st到ma潜ch浑.c托om添/b偶bs税/f究or车um亿.p借hpht职tp公:/趁/w委ww嚼.y甘st伤co此de狂.c守om数/b愚bs盏/f孕or互um羞.p悉hp当n贱规模太较大播时的惑双循少环设岂计，吩时间影复杂踩度为依O(炭mn洗)，悟空间邀复杂薪度为彼O(以m)池。显茎然m视>n还，把尚m换协算为躬n，两注意摧到m告数量侨级平乒均为迫n*拉lg往n，琴因而拒时间桃复杂堤度为斤O(刚n^絮2l预og哑n)旧，空跪间复狗杂度塔为O喊(n冠lo蛙gn层)。注意彩：同样效是精马确求司解n单的阶筝乘n演!，取求解倾范围纸的差缺异导暗致了妻算法辞设计次及其育复杂尽性的泊不同狂。大父规模磨n情辽形下宗精确归求解肠，算誓法的扶时间最复杂笨度与听空间峡复杂镜度都松要高跑于小赴规模浸情形拍的算孩法。颂或者辛说，战扩大趁n!医精确贡求解欧的范缓围，必是以洋提高虹算法随的时饮间复晚杂度骂与空育间复储杂度斜为代却价的赛。1.恶4凯算库法与雨程序缎设计计算距机的壤一切购操作槐都是膨由程辆序控沟制的负，离载开了孩程序富，计扯算机宅将一纺事无持成。贤从这砌个意征义来斗说，如计算有机的拜本质那是