算法概念介绍和举例说明.pptVIP

例子:给定两个正整数m和n,求它们的最大公因子 算法:欧几里德算法 输入:正整数m、n 输出：m和n的最大公因子;S1:保证m=n,如果mn，则m、n的值互换，否则转S2. S2:求余数。令r=m mod n,（0=rn) S3:判断余数r是否为0。如果r是0，则算法终止，n为答案，否则转S4. S4:置换。即m?n,n?r,转S2.;二、算法的特征 1、确定性 2、能行性 3、输入 4、输出 5、有穷性:一个算法总是在有限步之后结束，且每一步都可在有穷时间内完成. ; 一个算法总是在执行了有穷步骤的运算后终止，否则就是一个计算过程。 ;1.2 算法设计的步骤; 在模型建立好了以后，应该依据所选定的模型对问题重新陈述,并考虑下列问题: ;1;以货郎担问题为例：采用枚举法。 分析：;Salesman (n) i? 1;tour?0;min?∞ while i=(n-1)! do { p?PHRMUTI(n-1,i); // PHRMUTI(n-1,i)是生成1到n-1的第i个排列的子过程 cost(T(p))?EFP(c,T(p))； // EFP(c,T)是由费用矩阵c及路线T(p)所算得的总费用 if cost(T(p))min { tour?T(p); min?cost(T(p)) } i?i+1; } print min, tour ;四、算法的正确性 可以分两步考虑: (1)算法的终止性； (2)算法的每一步是否都正确 算法的正确性并不蕴涵算法的有效性。;六、文档的编制; ; ;; 就算法分析而言，一条语句的数量级指的是执行它的频率，而一个算法的数量级则指的是它所有语句执行频率的和。 确定一个算法的数量级是十分重要的，它在本质上反映了一个算法所需要的计算时间。;四、计算时间的渐进表示 假设某种算法的计算时间是f(n),其中变量n可以是输入或输出量，也可以是两者之和，还可以是它们之一的某种测度（例如，数组的维数，图的边数等等）。g(n)是在事前分析中确定的某个形式很简单的函数，例如，nm,logn,2n,,n!等。它是独立于机器和语言的函数，而f(n)则与机器和语言有关。;定义1.2 如果存在两个正常数c和n0，对于所有的n≥n0， |f(n)|≤c|g(n)| 则记作f(n)=Ο(g(n)). 因此，当说一个算法具有O(g(n))的计算时间时，指的是如果此算法用n值不变的同一类数据在某台机器上运行时，所用的时间总是小于|g(n))|的一个常数倍。所以g(n)是计算时间f(n)的一个上界函数，f(n)的数量级就是g(n)。;证明：取n0=1,当n=n0时，利用A(n)的定义和 一个简单的不等式，有 取c=|am|+….+|a0| 定理得证. 事实上，只要将n0取得足够大，可以证明只要c是比|am|大的任意一个常数，此定理都成立。; 此定理表明，变量n的固定阶数为m的任一多项式，与此多项式的最高阶nm同阶，因此计算时间为m阶的多项式的算法，其时间都可用O(nm).例如，若一个算法有数量级为c1nm1, c2nm2,…, cknmk 的k个语句，则此算法的数量级就是 c1nm1 +c2nm2+…+cknmk 由定理1.1，它等于O(nm),其中m=max{mi|1≤i ≤k};;定义1.3 如果存在两个正常数c和n0,对于所有n n0,有 |f(n)| ≥c|g(n)| 则记为f(n)=Ω(g(n))。 定义1.4 如果存在两个正常数c1 ,c2,和n0,对于所有的n n0,有 则记为f(n)=Θ(g(n))。 一个算法的f(n)=Θ(g(n))意味着该算法在最好和最坏情况下的计算时间就一个常因子范围内而言是相同的。;五、算法分类（按时间） 多项式时间算法：凡可用多项式来对其计算时间界限的算法。 指数时间算法：计算时间用指数函数界限的算法。; 注意：当数据集的规模很大时，要在现代计算机上运行具有比O（nlogn)复杂度高的算法往往是很困难的。;第二章 分治法 2.1 方法概述;4、 设计步骤 (1)分解：将原问题分解为若干个相互独立、与原问题形式相同的子问题； (2)求解：若子问题容易被解决则直接解，否则