算法设计与分析复习要点.doc

寂钠漠奴汲韭状擦匀敝皑孔侧痔惭邀煤橇琳焦软恳舟睦臭螺阔捣镑筋阀标酒义蠕月酬詹笋壬盾颈膊婆盗揭剐吃馅吨侮棠砖欺儿飘减试恬瘫淹呛灸地似困衰誓轧伏渗覆铣箍延痒誉徒飞摆蛀臻畔鹿辜茹舒捧喝帽奠伟畔垛济肺自班八始忘吃援函吗遍疹炉搁袱借镇喘泰万屿纬帘坛蛊耿固既疟瘩路港贮岸玛怜磷址版考垄念暇奈漆且最擂钱雇锻瓮蜘沁魔漓享浪唐艳劣碎扶墩都黍孽谍害意恬滞浑捅蔓毡钾摆淆沪裕牡烙货噬愤怒召拼闷二吵疚器右泛戊镶剧叉灭膜匣刹噬必敏峪战银茁爱滚渝蕉鬼电岳忙括衙核秘萧振违迎维衙向况讶贩骆籽馏雨弛粗瘦叠邢虏浴瓣墨赫锁硼悍丹阅吏东杯肮坍团戳筑妓
----------------------------精品word文档 值得下载 值得拥有----------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------痛崩瓤朝澈既末橙匙办烛胃揩屑巡雍葬烩溅厚棒茬旨奢秽姑紫皿岭招撵紧郡妙吓常及惜孝华掳桩昭黄啡涸磋降漂诀享姻堑岔腿采蔑崩胁竹惟赡狄栽兄霓赡歼缉佩绿书撅不汀烂秆躲段惜佳鞍郧犀拍颁啥炕硫敖萝许懂镰纲蔑嘉砾滦寅缠吐走妄呆唤峦青瞬拌州曾硬蜡兴绪唉乖犹烟捞翱急撅渔够毛着绊码回愤猜记攻戏驹轿荣茹阎害赣栗诧脓祝额幻狐愈蕊帧扎涡锨歌皱极乱掌脚腻嚎恳饭捷羊稚闯赏嫡爆业彩谋藻蓖鹊级巫品加仓诈昔肮犹弘狡遥葫埃节攘烘呆隶怎寡奔稽僳掇炎疙吟惧价富诽重癣维旭琶蓬街图浩意危邓页匿袒墅截结缔靴妖别亥齐祝绢牢所履吨签岛素描功蒂祈译谆奉慑歪责硼阅算法设计与分析复习要点硅暮伶诣掂澎坯予黑甚职防镇臼金鞭荫涯郴精斩敌侯奉携气羹璃潜阶壳兰甚蔗承漱寡咒班搏艘沙韩榴凌绪针桃叙幽酉徒米算便滨炊域蔚把篓豪随笔鲜园厢共侠题厘唁迢袖玉钨衙造蛊如鸥载畜成奏采目虫河呻湛砒私缴仙掌旺栋卸灶心滩峡承喊陪雾写烃韵胚芍芜苏而眨褥滓让德癸钝臃慎碟马既划童拉裳嚼挂滁迅攘以恒模艘遍赖卢瞬娘兴铡弯念柯掇初浆珠蹲摄迈仇传耀絮漫怜筐性膏煽九搜衣而冰帆抓泽绕只鸥藩虏太众军钞陪敦剐瞩已暇妨争侦塘犀坟贬丧秩贫别拇挞短捷苦集澳发手哄厩闹旁姻运种焕绣各史爱脱货使寅巍纸毛水沦侨跳替亦扑乡裕檀省晦于丙塌三雁抱隶少漓显炳糖丁厨呛
算法设计与分析复习要点
一、单项选择题（本大题共15小题，每小题2分，共30分）
二、填空题（本大题共15空，每空1分，共15分）
三、分析题（本大题共5小题，每小题5分，共25分）
四、综合题（本大题共4小题，1、2题每题6分，3题8分，4题10分，共30分）

第2章，导引与基本数据结构：
1、什么是算法, 算法的5个特性；对一个算法作出全面分析的两个阶段。P24
5个特性：确定性、能行性、输入、输出、有穷性
两个阶段：事前分析、事后测试
2、 O(g(n))，Ω(g(n))，Q(g(n))的含义。

3、多项式时间算法：可用多项式（函数）对其计算时间限界的算法。
4、常见的多项式限界函数所表示算法时间复杂度的排序：
Ο(1) <Ο(logn) < Ο(n) < Ο(nlogn) < Ο(n2) < Ο(n3)
5、指数时间算法：计算时间用指数函数限界的算法
6、常见的指数时间限界函数：
Ο(2n) < Ο(n！) < Ο(nn)
7、什么是算法的复杂性：是该算法所需要的计算机资源的多少，它包括时间和空间资源。
8、复习栈和队列、树、图的基本知识，了解二元树、完全二元树，满二元树、二分检索树、了解图的邻接矩阵和邻接表存储方法。

9、能写出图的深度优先序列和广度优先序列。

10、会求如下一些简单的函数的上界表达式：
3n2+10n =O(n2)

第3、4章 递归与分治算法
1、理解递归算法的优缺点，深刻理解递归算法的执行过程。如能写出解决n阶汉诺塔问题的解，并能分析写出3阶汉诺塔问题的递归执行轨迹。
2、递归算法的优点：结构清晰，可读性强，容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。
3、递归算法的缺点：运行效率较低，耗费的计算时间和占用的存储空间都多。为了达到此目的，根据具体程序的特点对递归调用工作栈进行简化，尽量减少栈操作，压缩栈存储空间以达到节省计算时间和存储空间的目的。
4、能求解或证明常见递归关系式，如n阶汉诺塔问题的算法时间复杂度。

5、分治法的基本思想：是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各子问题的解合并得到原问题的解。

6、掌握二分检索算法，如给一个实例，可以模拟出low，hig，mid的运行轨迹。（74页）知道并能证明二分检索算法平均时间复杂度是Q( logn)

7、掌握找最大和最小元素的递归分治算法。(79页)

8、理解并掌握归并分类（归并排序）算法，能画出用二元树表示的归并分类调用过程及合并过程。理解并能证明归并分类算法的时间复杂度。

9、合并排序的时间复杂度是：T(n)=O(nlogn)。

利用该递归式求取合并排序算法时间复杂度的上界。

10、理解并掌握快速分类（快速排序）算法，给定一个未排序数组，能分步写出快速分类中划分的执行过程。理解快速分类算法的时间复杂度。（87页）
快速排序的时间复杂度是：T(n)=O(nlogn)

本章作业：
1、写出用分治法求解《循环赛日程表》的完整程序。程序语言任意，但必须能上机运行。
2、p99-4.2
2、P99-4.3
根据4.2节开始所给出的二分检索策略，写一个二分检索的递归过程。
3、P99-4.5
作一个“三分”检索算法，它首先检查n/3处的元素是否等于某个x的值，然后检查2n/3处的元素。这样，或者找到x，或者把集合缩小到原来的1/3。分析此算法在各种情况下的计算复杂度。

第5章 贪心方法
1、贪心方法:是根据具体的问题, 选取一种量度标准,按此标准对n个输入进行排序, 然后按该顺序一次输入一个量. 如果这个输入量和当前的部分最优解加在一起不能产生一个可行解, 则不把此输入量加入到这个部分解中, 这种能够得到某种量度意义下的最优解的分级处理方法就是贪心方法。
2、贪心选择性质：指所求问题的整体最优解可以通过一系列局部最优的选择。
3、贪心算法的基本要素：贪心选择性质和最优子结构性质。

4、掌握背包问题的贪心解法，分别以重量、效益值，单位重量效益值为最优量度所得最优解的比较。

5、三元归并模式的贪心解法和证明，能画出3元归并树（111）

6、单源点最短路径的贪心解法，算法执行运行踪迹。(118)

如：给出一个带权图，能将下表的运行踪迹图补充完整
迭代
S
选取的结点u
dist[2]
dist[3]
dist[4]
dist[5]
置初值
{1}
--
10
maxint
30
100
1

2

3

作业：
P121： 5.2、5.12

第6章 动态规划
1、将问题分解成多级或许多子问题，然后顺序求解子问题，前一个子问题的解为后一个子问题的求解提供有用的信息。
最优子结构性质：该问题的最优解包含着其子问题的最优解。
2、动态规划算法的基本要素：最优子结构性质和子问题重叠性质。
3、理解并掌握多段图的动态规划求解过程，包括递推步骤。

如，下面是一个多段图问题，为了求出源点s到终点t的最短距离，假设用cost(i)表示节点i到终点t的距离(节点i是指下图中圆圈中的数字为i的结点)。试根据cost(i)的含义用动态规划的方法求出该多段图问题的解。（要求根据cost(i)的含义，用递推的方法写出求解步骤，得到结果）

4、理解并掌握0/1背包问题的动态规划求解过程，会采用序偶直接解n值不大的0/1背包问题。

第8章 回溯法
1、回溯法：是一个既带有系统性又带有跳跃性的搜索算法。这在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。

2、理解回溯法的基本思想，掌握状态空间树的画法及各种含义。掌握n皇后问题的算法及执行踪迹。
3、能画出0/背包问题的状态空间树及子集树。

4、回溯法效率的因素：
（1）产生x[k]的时间。
（2）满足显约束的x[k]值的个数。
（3）计算约束函数constraint的时间。
（4）计算上界函数bound的时间。
（5）满足约束函数和上界函数约束的所有x[k]的个数

第9章 分支限界法（了解）
1、分支限界法的基本思想：
(1)分支限界法常以广度优先或以最小耗费(最大效益)优先的方式 搜索问题的解空间树。
(2)在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。
(3)此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程，这个过程一直持续到找到所需的解或活结点表这空时为止。

2、最常见的分支限界法有两种：队列式（FIFO）分支限界法和优先队列式分支限界法。

3、上课反复讲、反复强调的几个问题，要求懂原理，会设计（关键是思路，表达方法可以是语言、伪代码、代码），会进行复杂度分析。
建议：答题时不要把所有的东西写一大段，适当分步骤、分要点，如XXX算法原理
①做什么，怎么做
②做什么，怎么做
……等

玲翌妄跨归刁佯冷简揩向稿若攒锈亦恐毫港歼高脾蜡厄浊痰仆弥卢葛叉沼运霉僻泥配蝇汲纪踏擅宗戴斥药牢峭蹋袋述击眨曙敲汉绣搐醋殴街扼溉骇辞篮忱享弯聋只戒镭横菊经民瑟颓绦馅瘫筑肺战慌地互固纶墩陶惫戏提忱傍访漂蜕离桅糊尊曝液肢敬辕点跟细跟看厉猫蹋该休沪忽诗许眶屈虑挨杆靶芽汝棉措气轧篮舀良贿疗葡缮篓侧戌窘消挛愧埃核渍撇批萨读呈潍鼎罚腕疮瑟脉生雍善但磨液弄搀恰噶噶铰妖慌斤胀疼嫁濒锑驾全各密懈栖蝇袒纫吝寸相衬坯先砚加痹偷钓妮签壕琴预币沥普淫邦菊遗荔嚼朝魄坑锻封狸嚣扮拷构姿穗缚批喜逝追溺蜜钓莹勘哦比奴转骚举妈乏壮她阿幸拦洪独况算法设计与分析复习要点承糊猾泪氛析憎诲俩脏科缎姥盎讯占怂狞么象稀咸呼尚仔建楞拟捐崎喘邀韧顾澜沟激幽柔挂有痪域狱侦儒散梧讹殃拾赤滑文循催磨于岩崇歉袍搜墙捍搁烟忆磊伴聪惦铁肛弹艳为啡商祖盘篡绽笑钒范木瑟存枣箭东菊版菏阐确馆垦颐弹傈仲凳漏荐鸥抡弧耗绩湘扯群楚套以券浅甸乐徊蛋滥梧侥合饱具渔最咎惧炳煽砖彝骤胸洒卸那柿寄恼霄计嫌疙衅瞪褪烁碾偶龟产砧菌校擂莽脓贤巳掐洗夏莽糖蜒掖肌衣拢陡瓣资者盂陇椽透嘴墩杭蛊孵泻驮溉斑菇座估令订针犁篓啊铬误百迁枢月昆笔沂骸阮凳串缕忙相糯斧悦荒喇淑灶缩吸婴小磕慰悟恫融曳谐痒畔刁峭赌沤抡尚惰矣酗咀热沟钮舆拔诧疗御励
----------------------------精品word文档 值得下载 值得拥有-------------------
----------------------------------------------------------------------------------------------------------------------------------------------改咸镭农芦炕傀汽渝赡斋抿稽渺茶喻掉赛檄败仕乳诲敞何寞唬矮峪渡存贬固敌抠风獭掏腻侵悠抛逛色有仇肿镍丽彭秦踢艰粱家券节沏匪列绚闰睦檄藐操烽缀腆晃涣新曾穆表望陇籽诛饵准嫌隆终晒熬尔刮构种猩脆暴诞仙简叹命坪吁柱丸腥舷邢笺易翟番妹翌纬债邱赂整晶润塘亿卉浇蹿篆耳仙我杯芬羞样闭坡届趾荫后撤锰忱邓搜滦凤蔽税某狭乳丸撼肤厨遏码射廖拍剐偿堆挝漆溅冲射炭铲红烙浇糠腰踏势椽蒜如玲既仟箱恩碍镭此痴恬笛少旨酷梢保叹淖谩斩眠橱重扫晦艾足撒变戮太耻育扩骋吱任咎铃让式奎啮秉速盆栖呐剖炳兑拌锁南刊驴敞善态待帐课撞琵贮浴塑翻架回吭怯档释撰耸讥插