算法设计与分析本书主要内容本书主要内容（续）第1章绪论1.1算法的基本概念问题的求解过程：分析问题→设计算法→编写程序→整理结果程序设计研究的四个层次：算法→方法学→语言→工具1.1.2算法及其重要特性算法的五大特性：欧几里德算法1.1.3算法的描述方法①输入m和n；②求m除以n的余数r；③若r等于0，则n为最大公约数，算法结束；否则执行第④步；④将n的值放在m中，将r的值放在n中；⑤重新执行第②步。⑵流程图优点：流程直观缺点：缺少严密性、灵活性使用方法：描述简单算法注意事项：注意抽象层次N⑶程序设计语言优点：能由计算机执行缺点：抽象性差，对语言要求高使用方法：算法需要验证注意事项：将算法写成子函数#include<iostream.h>intCommonFactor(intm,intn){intr=m%n;while(r!=0){m=n;n=r;r=m%n;}returnn;}voidmain(){cout<<CommonFactor(63,54)<<endl;}⑷伪代码——算法语言伪代码（Pseudocode）：介于自然语言和程序设计语言之间的方法，它采用某一程序设计语言的基本语法，操作指令可以结合自然语言来设计。优点：表达能力强，抽象性强，容易理解使用方法：7±21.r=m%n;2.循环直到r等于02.1m=n;2.2n=r;2.3r=m%n;3.输出n;1.1.4算法设计的一般过程1.1.5重要的问题类型1.2算法分析1.2算法分析时间复杂性分析的关键：问题规模：输入量的多少；基本语句：执行次数与整个算法的执行时间成正比的语句1.2.1渐进符号2.大Ω符号3.Θ符号例：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＋1≥5n2则：5n2＋8n＋1＝Θ(n2)1.2.2最好、最坏和平均情况最好情况：出现概率较大时分析最差情况：实时系统平均情况：已知输入数据是如何分布的，通常假设等概率分布1.2.3非递归算法的分析非递归算法分析的一般步骤：1.2.4递归算法的分析2.扩展递归技术3.通用分治递推式1.2.5算法的后验分析一般步骤：1.明确实验目的2.决定度量算法效率的方法，为实验准备算法的程序实现3.决定输入样本，生成实验数据4.对输入样本运行算法对应的程序，记录得到的实验数据5.分析得到的实验数据表格法记录实验数据1.3实验项目——求最大公约数3.实验要求⑴至少设计出三个版本的求最大公约数算法；⑵对所设计的算法采用大O符号进行时间复杂性分析；⑶上机实现算法，并用计数法和计时法分别测算算法的运行时间；⑷通过分析对比，得出自己的结论。