2006 算法设计qiu-lec1&2

《2006 算法设计qiu-lec1&2》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、参考教材算法设计与分析¢ThomasH.Cormen，《算法导论，第二AlgorithmsDesign&Analysis版》，高等教育出版社（影印，英文）。¢吴伟昶，《算法设计技巧与分析》，电子工业第一讲：概述出版社，2005。提醒：不看教材很难会有好成绩华中科技大学软件学院光看教材不保证有好成绩邱德红主讲2005年4月提醒：不看教材很难有好基础光看教材很难有好发展12课程训练内容从简单的问题开始¢相关基本概念•求集合中的极小值¢算法设计方法¢算法分析技术1(1,4,9)¢解决实际问题的能力(5,2,3,7,2)2注意：(6,5,3)不包含算法在某种具体语言下的实现不包含算法调试(2,2,6,

2、8)3是一门理论基础课程编程实现是你自己的事情（Programimplementationsareonyourown）34解决问题数据结构（DataStructure）¢输入、输出和数据结构直接相关InputAlgorithmsOutput¢数据之间的逻辑关系、数据在计算机上的存储方式、数据的操作。三要素：输入、输出、算法¢数据结构与算法设计是密切相关的算法在解决问题层面上具有“黒盒”特征561算法（Algorithm）算法表述¢Informally,analgorithmisanywell-definedcomputationalprocedurethattakessomevalue,ors

3、etofvalues,asinputandproduces¢自然语言（ENGLISH）somevalue,orsetofvalues,asoutput.¢算法描述语言（Pseudo-code）¢计算机程序语言(C++,Java)¢Analgorithmisastep-by-stepdescriptionofaprocedurewhich,iffollowedclosely,¢硬件设计（DSP）producesawell-definedresult.¢算法是为了求解问题而给出的指令序列。程序只是算法的一种实现78算法一般特性算法一般特性¢正确性：对于符合输入类型的任意输入数据，都产生正确¢有效性

4、：每一步指令能够被有效的执行，的输出。并且规定了指令的执行效果，结果应该具¢Example:Givenanelectionof100,000,000votes,有的数据类型，而且是可以预期的。determinethewinner.（选举统计）Approach1:Countall100,000,000votes!¢确定性：每一步之后都要有确定的下一步Approach2:Selectasampleof1000,000votesanddeclarethewinnerofthesampleasthewinnerofthe指令。election.¢有穷性：有限步内结束==>withhighprobabi

5、lity,approach2willdeterminethewinnercorrectly!Butnotalways.(但是可以获得很高的正确性概率)910算法效率（Efficiency）资源开销与输入¢Resourceconsumptiondiffersdependingonthesizeof¢有限资源theinput(资源开销与输入大小相关)Computationalresources：lengthoftext(文本长度)•CPUtime(runningtime)计算时间numberofrecordstobesorted(排序记录条目数量)•memoryusage(space)存储空间¢R

6、esourceconsumptionmayevendiffergreatlyforinputs•messagessentalongthenetwork网络带宽ofthesamesize,dependingontheirstructure(资源开销与输入的组织结构有关)highlyunsortedinput(无序)¢Theseresourcesshouldbeusedwisely，andalgorithmsthatareefficientintermsoftimeoralmostsortedinput(有序)spacewillhelpyoudoso。(效率分析是为了有效的利¢Specifyres

7、ourceconsumptionasafunctionofthe用资源)inputssize.随输入规模变化的资源开销函数11122时空资源折中原理¢对于同一个求解问题，一般会存在多种算法，算法设计与分析这些算法在时空开销上的优劣往往表现出“时AlgorithmsDesign&Analysis空折中”的性质，即为了改善一个算法的时间开销，往往可以通过增大空间开销为代价，设第二讲：算法渐进分析计出一