算法引论及简单算法

《算法引论及简单算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、补充材料1算法引论及简单算法清华大学自动化系刘连臣2010年11月1日计算机语言与程序设计基础1注意算法是程序设计的灵魂2与数据结构的区别：考虑问题的角度：数据结构关心不同的数据结构在解题中的作用和效率；算法关心不同设计技术的适用性和效率。考虑问题的高度：数据结构关心的是解具体问题，算法不仅如此，它提供一种解决问题的通用方法。与其他课程的关系高级程序设计语言（C语言，等）数据结构算法设计与分析系统的设计与实现3主要内容目标：了解算法分析的基本含义。掌握查找算法、排序算法、递推算法等算法理念。提纲补1.1算法分析补1.2

2、查找算法补1.3排序算法补1.4递推算法4补1.1算法分析前面的课程内容以C语言语法为主本补充章介绍一些基本算法大家在编写程序的时候，“八仙过海，各显神通”，解决同一个问题，可以使用各种方法。算法之间存在着“优劣”之分5补1.1算法分析1、算法分析的目的通过对算法分析，在把算法变成程序实际运行前，就知道为完成一项任务所设计的算法的好坏，从而运行好算法，改进差算法，避免无益的人力和物力浪费。6补1.1算法分析2、算法分析的含义算法分析是一种分析技术，它以独立于具体的硬件平台、编译器和编程语言的方式，来描述算法的执行行为，

3、即它关心的是算法，而不是程序。算法分析是一种测量算法的性能的方法，它不关心精确的细节，如在算法的某次运行中总共执行了多少条机器指令，而是想要一个大致的估计，即随着输入数据规模的增大，算法所需工作量以何种速度递增。（关心变化趋势）7补1.1算法分析3、算法复杂性时间复杂性和空间复杂性8补1.1算法分析1.有些计算机需要用户提供程序运行时间的上限，一旦达到这个上限，程序将被强制结束。2.正在开发的程序可能需要提供一个满意的实时响应。为什么要考虑时间复杂性？91.多用户系统中运行时，需指明分配给该程序的内存大小。2.可提前知

4、道是否有足够可用的内存来运行该程序。3.一个问题可能有若干个内存需求各不相同的解决方案，从中择取。4.利用空间复杂性来估算一个程序所能解决问题的最大规模。考虑程序的空间复杂性的理由：补1.1算法分析104.如何进行算法分析？事前分析：就算法本身，通过对其执行性能的理论分析，得出关于算法特性——时间和空间的一个特征函数（Ο）——与计算机软硬件没有直接关系。事后测试：将算法编制成程序后放到计算机上运行，收集其执行时间和空间占用等统计资料，进行分析判断——直接与物理实现有关。补1.1算法分析111）事前分析目的：试图得出关于

5、算法执行特性的一种形式描述，以“理论上”衡量算法“好坏”。如何给出反映算法执行特性的描述？最直接方法：统计算法中各种运算的执行情况：运用了哪些运算每种运算被执行的次数该种运算执行一次所花费的时间算法的执行时间=∑Fi*ti补1.1算法分析12估算执行时间的方法选择一种或多种（如加、乘和比较等），然后确定这种（些）操作分别执行了多少次。令n代表程序实例特征，则执行时间计算公式为：TP（n）=c1ADD(n)+c2SUB(n)+c3MUL(n)+c4DIV(n)+···c1、c2、c3、c4分别表示一次加、减、乘、除操作所

6、需的时间。函数ADD(n)、SUB(n)、MUL(n)、DIV(n)分别表示程序P中，所使用的加、减、乘、除操作的次数。这种方法是否成功取决于识别关键操作的能力，这些关键操作对时间复杂性的影响最大。一条语句在整个程序运行时实际执行时间=频率计数*每执行一次该语句所需的时间补1.1算法分析13频率计数：算法中语句或运算的执行次数。例：x=x+yfor(i=1;i<=n;i++)for(i=1;i<=n;i++)x=x+y;for(j=1;j<=n;j++)x=x+y;(a)(b)(c)分析：(a)：x=x+y执行了1次(

7、b)：x=x+y执行了n次(c)：x=x+y执行了n2次注：在事前分析中，只限于确定与所使用机器及其他环境因素无关的频率计数，依此建立一种理论上分析模型。补1.1算法分析14数量级语句的数量级：语句的执行频率。例：1，n，n2算法的数量级：算法包含所有语句的执行频率之和。算法的数量级从本质上反映了一个算法的执行特性。例：求解同一问题的三个算法分别具有n,n2,n3数量级。若n=10，则可能的执行时间将分别是10，100，1000个单位时间——与环境因素无关。补1.1算法分析15补1.1算法分析5、算法复杂性的等级常量阶

8、时间复杂度为O(1)算法运行时间不随着问题的规模而变化如：简单的赋值语句，x=y;算术运算，x=y*5+z%3;固定次数的循环语句等for(i=0;i<10;i++)for(j=0;j<20;j++)a[i][j]=0;16补1.1算法分析线性阶时间复杂度为O(n)算法运行时间随着问题的规模而成线性变化for(i=0;i