算法概念介绍及举例说明ppt课件.ppt

《算法概念介绍及举例说明ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、例子:给定两个正整数m和n,求它们的最大公因子算法:欧几里德算法输入:正整数m、n输出：m和n的最大公因子第一章算法引论1.1算法的基本概念一、什么是算法及其与程序的区别S1:保证m>=n,如果m

2、输入4、输出5、有穷性:一个算法总是在有限步之后结束，且每一步都可在有穷时间内完成.算法与程序的区别：程序：与某种语言有关，能直接在机器上运行。算法：与特定的语言无关，可用任何语言实现，甚至可以用自然语言实现，但是一般为了避免二义性，本书采用类C语言描述。一个算法总是在执行了有穷步骤的运算后终止，否则就是一个计算过程。有穷性与有效性的关系：三、评价算法的标准有穷性是对算法的基本要求，如果一个算法要能使用，必须具有有效性。有效性是指算法在规定的时间里终止。时间复杂性和空间复杂性1.2算法设计的步骤一、问

3、题的描述例:货郎担问题设售货员在一天内要到5个城市去推销货物，已知从一个城市到其他城市的费用，求总费用最少的路线。给出的信息主要有五个城市的关系图及相应的费用矩阵。二、模型的拟制建模阶段至少要考虑以下两个基本问题：1）最适合于这个问题的数学结构是什么？2）有没有已经解决了的类似问题可供借鉴？在模型建立好了以后，应该依据所选定的模型对问题重新陈述,并考虑下列问题:(1)模型是否清楚地表达了与问题有关的所有重要的信息?(2)模型中是否存在与要求的结果相关的数学量?(3)模型是否正确反映了输入、输出的关系?

4、(4)对这个模型处理起来困难吗？152434724335211对于货郎担问题，其数学模型是带权图，与此图相关的是费用矩阵。以货郎担问题为例：采用枚举法。分析：三、算法的详细设计算法的详细设计是指设计求解某个具体问题的一系列步骤，并且这些步骤可以通过计算机的各种操作来实现。输入：城市数目n;费用矩阵C=(cij)n*n输出：旅行路线TOUR;最小费用MINSalesman(n)i1;tour0;min∞whilei<=(n-1)!do{pPHRMUTI(n-1,i);//PHRMUTI(n-1,

5、i)是生成1到n-1的第i个排列的子过程cost(T(p))EFP(c,T(p))；//EFP(c,T)是由费用矩阵c及路线T(p)所算得的总费用ifcost(T(p))

6、）对输入/输出的要求（4）正确性证明（5）时间复杂性和空间复杂性的分析二、算法分析的要点1、确定使用的运算和执行这些运算所用的时间。运算分为两类(1)基本运算；(2)“组合”运算—由基本运算组成。1.3算法分析一、算法分析的原因1、为了对算法的某些特定的输入，估计或限界该算法所需要的空间和运行时间。2、为了建立衡量算法优劣的标准，用以比较同一问题的不同算法。时间是固定量时间是变化量2、确定能反映出算法在各种情况下工作的数据集—构造出能产生最好、最坏和有代表性情况的数据配置。三、算法分析的两个阶段1、事

7、前分析—求出该算法的一个时间限界函数。2、事后测试—收集此算法的执行时间和实际占用空间的统计资料。频率计数：语句执行的次数。--事前分析仅限于确定每条语句的频率计数。因为它与所用的机器无关，同时独立于编写此算法的程序设计语言。例如：fori1tondoxx+yrepeatfori1tondoforj1tondoxx+yrepeatrepeatxx+y就算法分析而言，一条语句的数量级指的是执行它的频率，而一个算法的数量级则指的是它所有语句执行频率的和。确定一个算法的数量级是十分重要的，它在本

8、质上反映了一个算法所需要的计算时间。四、计算时间的渐进表示假设某种算法的计算时间是f(n),其中变量n可以是输入或输出量，也可以是两者之和，还可以是它们之一的某种测度（例如，数组的维数，图的边数等等）。g(n)是在事前分析中确定的某个形式很简单的函数，例如，nm,logn,2n,,n!等。它是独立于机器和语言的函数，而f(n)则与机器和语言有关。定义1.2如果存在两个正常数c和n0，对于所有的n≥n0，

9、f(n)

10、≤c

11、g(n)

12、则记作f(n)=Ο(g(