算法概述算法概述

《算法概述算法概述》由会员分享，可在线阅读，更多相关《算法概述算法概述（80页珍藏版）》请在金锄头文库上搜索。

1、算法分析与设计,杨秋妹 ,教材：计算机算法设计与分析 王晓东 编著 电子工业出版社 出版,参考教材,严蔚敏等著，数据结构，清华大学出版社 Thomas H.Cormen等著算法导论，机械工业出版社,成绩,期末考试：70% 期中考试：无 平时成绩：30% 考勤 实验 综合性实验,在线做题,http:/ http:/ 培养良好的程序设计习惯和风格 学习常用的、有代表性的算法 培养分析算法时间和空间复杂度的初步能力,程序=数据结构+算法,乘汽车旅行的人总希望找出到目的地的尽可能的短的行程。如果有一张地图并在图上标出每对十字路口之间的距离，如何找出这一最短行程？,建立解题模型数据结构 解决方法算法,什

2、么是算法,算法是一系列的计算步骤，用来将输入数据转换成输出结果。 算法是一个有穷的解决问题的指令序列。每条指令都必须有清楚的含义并且在有穷长的时间内用有穷的动作完成。 一个算法无论接受任何输入，都必须在有穷步内停止。,排序问题,输入：由n个数构成的一个序列 输出：对输入序列的一个排列（重排），使得a1=a2=an 算法：插入排序，冒泡排序，快速排序，合并排序等,算法是用来解决一类计算问题的，注意是一类问题，而不是一个特定的问题。 例如，一个排序算法应该能对任意一组数据进行排序，而不是仅对int a = 1, 3, 4, 2, 6, 5 ;,void sort(void) a0 = 1; a1

3、= 2; a2 = 3; a3 = 4; a4 = 5; a5 = 6; ,算法的描述,自然语言； 程序设计语言； 类程序语言,选择排序算法的自然语言描述,排序过程 首先通过n-1次关键字比较，从n个记录中找出关键字最小的记录，将它与第一个记录交换 再通过n-2次比较，从剩余的n-1个记录中找出关键字次小的记录，将它与第二个记录交换 重复上述操作，共进行n-1趟排序后，排序结束,选择排序算法的C语言描述,void selectSort(int a,int n) int i,j,min,temp; for(i=0;in-1;i+) min=i; for(j=i+1;jn;j+) if(ajami

4、n) min=j; if(min!=i) temp=amin; amin=ai; ai=temp; ,算法的几个特性,算法是指解决问题的一种方法或一个过程。 满足性质： (1)输入：有零个或多个外部提供的量作为算法的输入。 (2)输出：算法产生至少一个量作为输出。 (3)确定性：组成算法的每条指令是清晰，无歧义的。 (4)有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。,什么是程序,程序是算法用某种程序设计语言的具体实现 程序可以不满足算法的有穷性,算法可以解决的问题,因特网快速地访问和检索大量的信息,搜索引擎三段式工作流程,搜集 批量搜集，增量式搜集；搜集目标，搜集策

5、略 预处理 关键词提取；重复网页消除；链接分析； 服务 查询方式和匹配；结果排序；文档摘要,搜集,整理,服务,电子商务保持信用卡号、密码、银行结单等信息的私密性，公共密钥加密技术和数字签名技术,算法可以解决的问题,制造业和其他商业应用中，是否能最有效地分配稀有资源，例如，石油公司确定在何处打井，以求最大化预期效益；美国总统候选人希望确定该把宣传的资金花在何处，以求赢得竞选的可能性最大；,算法可以解决的问题,常用的基础算法,递归法（Recursion） 分治法(Divide-and Conquer)、 贪心法(Greedy) 动态规划(Dynamic Programming)、 回溯（Backt

6、racking） 分支限界法（Branch and Bound） 近似算法(Approximation),问题求解,理解问题,精确解或近似解 选择数据结构 算法设计策略,设计算法,算法的设计目标,算法应易于理解、编程和调试 算法应尽可能有效地利用计算机的资源，特别地，应尽可能快地运行,好算法的判断标准,1.正确性 2.健壮性 3.时间复杂性 4.空间复杂性 5.可读性 6. 灵活性（Flexibility）、可重用性(Reuseabale)等,算法复杂度分析,算法复杂性,体现在运行该算法所需要的计算机资源多少上 所需资源越多，该算法的复杂性越高 所需资源越少，该算法的复杂性越低,时间复杂性：算

7、法执行需要的时间资源 空间复杂性：算法执行需要的空间资源,实验测量法（实际执行时间、执行指令的条数） 把算法用某种程序设计语言实现并在计算机上运行，计算实际运行时间,如何进行算法时间复杂性分析,例：让一台更快的、运行插入排序的计算机（计算机A）与一台较慢的、运行合并排序的计算机（计算机B）进行比较。两者都要对一个大小为一百万个数的数组进行排序。假设计算机A每秒能执行10亿条指令，而计算机B每秒只能执行一千万条指令。,计算机A花费的时间： （106）2条指令/109条指令/秒1000秒 计算机B花费的时间： 106lg106条指令/107条指令/秒2秒,影响实验测量时间的因素,程序的输入长度 编

8、译程序生成目标代码的质量 计算机指令的质量和速度 算法本身的优劣,实验测量法（实际执行时间、执行指令的条数） 缺点： 必须先运行根据算法编制的的程序；所得的时间统计量依赖于计算机的硬件、软件等环境因素，容易掩盖算法本身的优劣。,事前分析(估计)法 忽略机器性能对运行时间的影响 使用问题输入规模为参数的函数来衡量,算法执行的时间是算法优劣和问题规模的函数。评价一个算法的优劣，可以在相同的规模下，考察算法执行时间的长短来进行判断。,选定输入规模,规模越大，需要的运行时间越长 使用以算法输入规模n为参数的函数T（n）研究算法效率,运行时间的度量单位,时间的标准度量单位，如秒、毫秒。缺点：依赖特定计算

9、机的运行速度 统计每一步操作的总共执行次数 找出算法中最重要的操作基本操作，计算它们的运行次数 基本操作通常是算法最内层循环中最费时的操作,例：A是一个由 n个不同元素的实数数组，给出求其最大和最小元素的算法和时间复杂性 void MinMax(double A, int n, double max, double min ) double max, min; max=min=A0; for ( k=1; kmax ) max=Ak; if ( Akmin ) min=Ak; ,T（n） 2（n1）,评价算法运行时间的标准,最好时间复杂度 算法对具有长度为n的任何输入的最短运行时间 最坏时间复

10、杂度 算法对具有长度为n的任何输入的最长运行时间 平均时间复杂度 在平均输入下，算法的运行时间。通常假设给定长度的各种输入概率相同。,例:A是一个由n个不同元素的实数数组，给出确定给定实数K是否在A中的算法及其时间复杂性,SequentialSearch(A0n-1,K) i = 0 while i n and Ai != K do i = i + 1 if i n return i else return -1 ,最好时间复杂度T（n）1 最坏时间复杂度 T（n） n 平均时间复杂度 T（n）p（n1）/2n（1p）,常用最坏运行时间估计,平均运行时间难以计算 假设每一个输入具有相同的概率有

11、时没有意义 平均运行时间常常与最坏运行时间有相同的数量级 实际问题中，算法的运行时间常常达到这个上界,渐近时间复杂性,指当问题规模趋向无穷大时，该算法时间复杂度的数量级,一般说来，当n单调增加且趋于时，T（n）也将单调趋于 对于T（n），如果存在g（n），使得当n 时，有 T（n） g（n）/ T（n）0 那么，我们说g（n）是T（n）当n趋于时的渐进复杂性,T(n)= 3n2+4nlogn+7 g(n) = 3n2 当n ，T（n) g（n） g（n）比T（n）简单 直观上， g（n）是T（n）略去低阶项所留的主项,几个常见的渐进符号,渐近上界符号O 渐近下界符号 紧渐近界符号,渐进符号,渐

12、近上界符号O f（n） O（g（n）的成立条件是： 对于所有足够大的n，f（n）的上界由g（n）的常数倍所确定，即存在大于0的常数c和非负整数n0，使得： 对于所有n n0 ，有f（n） cg（n）,100n+5 O(n2),渐进符号,渐近下界符号 f（n） （g（n）的成立条件是： 对于所有足够大的n，f（n）的下界由g（n）的常数倍所确定，即存在大于0的常数c和非负整数n0，使得： 对于所有n n0 ，有f（n） cg（n）,n3 (n2),渐进符号,紧渐近界记号符号 f（n） （g（n）的成立条件是： 对于所有足够大的n，f（n）的上界和下界都由g（n）的常数倍所确定，即存在大于0的常数

13、c1、c2和非负整数n0，使得： 对于所有n n0 ，有c1g（n） f（n） c2g（n）,1/2n(n-1) (n2),根据O的定义，容易证明它有如下运算规则，如下这些规则也同样适用和表示法 ： (1) O(f)+O(g)=O(max(f,g)； (2) O(f)+O(g)=O(f+g)； (3) O(f)O(g)=O(fg)； (4) 如果g(N)=O(f(N)，则O(f)+O(g)=O(f)； (5) O(Cf(N)=O(f(N)，其中C是一个正的常数； (6) f=O(f)。,渐近分析记号的运算性质,算法的渐进时间复杂性,算法中基本操作重复执行的次数是问题规模n的某个函数f（n），算

14、法的时间度量记作T（n）= O（ f（n）。它表示随问题规模n的增大，算法执行时间的增长率不会超过f（n），称为算法的渐进时间复杂性，简称时间复杂性。,定理： 若 A（n）=amnm+a1n+a0 是关于n的m次多项式，则 A（n）=（nm） 此定理说明，当要比较的两个算法的渐进复杂性的阶不相同时，只要确定出各自的阶 如f(n) = 20n2 + 5n + 10 g(n) = 3n5 + 2n3 + 100,算法效率分析,非递归算法 递归算法,void selectSort(int a,int n) int i,j,min,temp; for(i=0;in-1;i+) min=i; for(j

15、=i+1;jn;j+) if(ajamin) min=j; if(min!=i) temp=amin; amin=ai; ai=temp; ,i=n-2 T(n) = n-(i+1)= n(n-1)/2 i=0 = O(n2),例:选择排序时间复杂度分析,分析非递归算法效率的通用方案,决定用哪个（哪些）参数作为输入规模的度量 找出算法的基本操作 检查基本操作的执行次数是否只依赖输入规模，如果还依赖其他特性则应区分最差、平均及最优效率 建立算法基本操作执行次数的求和公式 对求和公式求解，至少应确定其增长次数,递归算法的分析,一个过程在运行时直接或间接地调用自己，则该过程称为递归程序,例：计算阶乘函数F（n）,F(n) if n = 0 return 1 else return F(n-1)*n ,时间复杂度递归公式(乘法步数) T(n) = T(n-1) + 1 (n0) T(0) = 0,T(n) = n= O(n),例：归并排序,msort(int x,int aux,i