算法设计与分析王红梅第1章绪论

《算法设计与分析王红梅第1章绪论》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法设计与分析王红梅编著普通高校计算机专业特色教材精选本书主要内容第1章绪论第2章NP完全理论第3章蛮力法第4章分治法第5章减治法第6章动态规划法本书主要内容（续）第7章贪心法第8章回溯法第9章分支限界法第10章概率算法第11章近似算法第12章计算复杂性理论第1章绪论算法理论的两大论题：1.算法设计2.算法分析1.1算法的基本概念1.1.1为什么要学习算法1.1.2算法及其重要特性1.1.3算法的描述方法1.1.4算法设计的一般过程1.1.5重要的问题类型问题的求解过程：分析问题→设计算法→编写程序→整理结果程

2、序设计研究的四个层次：算法→方法学→语言→工具1.1.1为什么要学习算法理由1：算法——程序的灵魂理由2：提高分析问题的能力算法的形式化→思维的逻辑性、条理性1.1.2算法及其重要特性算法（Algorithm）：对特定问题求解步骤的一种描述，是指令的有限序列。算法的五大特性：⑴输入：一个算法有零个或多个输入。⑵输出：一个算法有一个或多个输出。⑶有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。⑷确定性：算法中的每一条指令必须有确切的含义，对于相同的输入只能得到相同的输出。⑸可行性：算法描

3、述的操作可以通过已经实现的基本操作执行有限次来实现。欧几里德算法mnr例：欧几里德算法——辗转相除法求两个自然数m和n的最大公约数1.1.3算法的描述方法⑴自然语言优点：容易理解缺点：冗长、二义性使用方法：粗线条描述算法思想注意事项：避免写成自然段①输入m和n；②求m除以n的余数r；③若r等于0，则n为最大公约数，算法结束；否则执行第④步；④将n的值放在m中，将r的值放在n中；⑤重新执行第②步。欧几里德算法⑵流程图优点：流程直观缺点：缺少严密性、灵活性使用方法：描述简单算法注意事项：注意抽象层次N开始输入m和n

4、r=m%nr=0m=n；n=r输出n结束Y欧几里德算法⑶程序设计语言优点：能由计算机执行缺点：抽象性差，对语言要求高使用方法：算法需要验证注意事项：将算法写成子函数#includeintCommonFactor(intm,intn){intr=m%n;while(r!=0){m=n;n=r;r=m%n;}returnn;}voidmain(){cout<

5、序设计语言之间的方法，它采用某一程序设计语言的基本语法，操作指令可以结合自然语言来设计。优点：表达能力强，抽象性强，容易理解使用方法：7±21.r=m%n;2.循环直到r等于02.1m=n;2.2n=r;2.3r=m%n;3.输出n;欧几里德算法1.1.4算法设计的一般过程1．理解问题2．预测所有可能的输入3.在精确解和近似解间做选择4.确定适当的数据结构5．算法设计技术6．描述算法7．跟踪算法8．分析算法的效率9．根据算法编写代码1.1.5重要的问题类型1.查找问题2.排序问题3.图问题4.组合问题5.几何问

6、题1.2算法分析1.2.1渐进符号1.2.2最好、最坏和平均情况1.2.3非递归算法的分析1.2.4递归算法的分析1.2.5算法的后验分析1.2算法分析算法分析（AlgorithmAnalysis）：对算法所需要的两种计算机资源——时间和空间进行估算时间复杂性（TimeComplexity）空间复杂性（SpaceComplexity）算法分析的目的：设计算法——设计出复杂性尽可能低的算法选择算法——在多种算法中选择其中复杂性最低者时间复杂性分析的关键：问题规模：输入量的多少；基本语句：执行次数与整个算法的执行时

7、间成正比的语句for(i=1;i<=n;i++)for(j=1;j<=n;j++)x++;问题规模：n基本语句：x++1.2.1渐进符号1.大O符号定义1.1若存在两个正的常数c和n0，对于任意n≥n0，都有T(n)≤c×f(n)，则称T(n)=O(f(n))n0问题规模n执行次数n0之前的情况无关紧要T(n)c×f(n)2.大Ω符号定义1.2若存在两个正的常数c和n0，对于任意n≥n0，都有T(n)≥c×g(n)，则称T(n)=Ω(g(n))n0问题规模n执行次数n0之前的情况无关紧要T(n)c×g(n)1.

8、2.1渐进符号（续）3.Θ符号定义1.3若存在三个正的常数c1、c2和n0，对于任意n≥n0都有c1×f(n)≥T(n)≥c2×f(n)，则称T(n)=Θ(f(n))n0问题规模n执行次数n0之前的情况无关紧要T(n)c2×f(n)c1×f(n)1.2.1渐进符号（续）例：T(n)＝5n2＋8n＋1当n≥1时，5n2＋8n＋1≤5n2＋8n＋n＝5n2＋9n≤5n2＋9n2≤14n2＝