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

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

1、第1章绪论算法理论的两大论题：1.算法设计2.算法分析1.1算法的基本概念1.1.1为什么要学习算法1.1.2算法及其重要特性1.1.3算法的描述方法1.1.4算法设计的一般过程1.1.5重要的问题类型问题的求解过程：分析问题→设计算法→编写程序→整理结果程序设计研究的四个层次：算法→方法学→语言→工具1.1.1为什么要学习算法理由1：算法——程序的灵魂理由2：提高分析问题的能力算法的形式化→思维的逻辑性、条理性1.1.2算法及其重要特性算法（Algorithm）：对特定问题求解步骤的一种描述，是指令的有限序列。算法的五大特性：⑴输入：一个

2、算法有零个或多个输入。⑵输出：一个算法有一个或多个输出。⑶有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。⑷确定性：算法中的每一条指令必须有确切的含义，对于相同的输入只能得到相同的输出。⑸可行性：算法描述的操作可以通过已经实现的基本操作执行有限次来实现。欧几里德算法mnr例：欧几里德算法——辗转相除法求两个自然数m和n的最大公约数1.1.3算法的描述方法⑴自然语言优点：容易理解缺点：冗长、二义性使用方法：粗线条描述算法思想注意事项：避免写成自然段①输入m和n；②求m除以n的余数r；③若r等于0，则n为最大公约数，算

3、法结束；否则执行第④步；④将n的值放在m中，将r的值放在n中；⑤重新执行第②步。欧几里德算法⑵流程图优点：流程直观缺点：缺少严密性、灵活性使用方法：描述简单算法注意事项：注意抽象层次N开始输入m和nr=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;}

4、voidmain(){cout<

5、踪算法8．分析算法的效率9．根据算法编写代码1.1.5重要的问题类型1.查找问题2.排序问题3.图问题4.组合问题5.几何问题1.2算法分析1.2.1渐进符号1.2.2最好、最坏和平均情况1.2.3非递归算法的分析1.2.4递归算法的分析1.2.5算法的后验分析1.2算法分析算法分析（AlgorithmAnalysis）：对算法所需要的两种计算机资源——时间和空间进行估算时间复杂性（TimeComplexity）空间复杂性（SpaceComplexity）算法分析的目的：设计算法——设计出复杂性尽可能低的算法选择算法——在多种算法中选择其中

6、复杂性最低者时间复杂性分析的关键：问题规模：输入量的多少；基本语句：执行次数与整个算法的执行时间成正比的语句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

7、问题规模n执行次数n0之前的情况无关紧要T(n)c×g(n)1.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＝O(n2)当n≥1时，5n2＋8n＋1≥5n2＝Ω(n2)∴当n≥1时，14n2≥5n2＋8n

8、＋1≥5n2则：5n2＋8n＋1＝Θ(n2)定理1.1若T(n)=amnm+am-1nm-1+…+a1n+a0（am>0），则有T(n)=O(nm)且T(n)=Ω(nm)，因此，