算法复杂性分析算法概述

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

1、算法概述,杨秋妹 ,程序=数据结构+算法,乘汽车旅行的人总希望找出到目的地的尽可能的短的行程。如果有一张地图并在图上标出每对十字路口之间的距离，如何找出这一最短行程？,建立解题模型数据结构 解决方法,什么是算法,算法是一个有穷的解决问题的指令序列。每条指令都必须有清楚的含义并且在有穷长的时间内用有穷的动作完成。 一个算法无论接受任何输入，都必须在有穷步内停止。,排序问题,输入：由n个数构成的一个序列 输出：对输入序列的一个排列（重排），使得a1=a2=an 算法：插入排序，冒泡排序，快速排序，合并排序等,算法的几个特性,算法是指解决问题的一种方法或一个过程。 满足性质： (1)输入：有零个或多

2、个外部提供的量作为算法的输入。 (2)输出：算法产生至少一个量作为输出。 (3)确定性：组成算法的每条指令是清晰，无歧义的。 (4)有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。,什么是程序,程序是算法用某种程序设计语言的具体实现 程序可以不满足算法的有穷性,算法的描述,自然语言； 程序设计语言； 类程序语言,算法可以解决的问题,人类基因的目标是找出人类DNA的所有十万种基因，确定构成人类DNA的30亿种化学基对的各种序列，将这些信息存储在数据库中，并开发出用于进行这方面数据分析的工具。 因特网快速地访问和检索大量的信息,电子商务保持信用卡号、密码、银行结单等信息的私

3、密性，公共密钥加密技术和数字签名技术 制造业和其他商业应用中，是否能最有效地分配稀有资源，例如，石油公司确定在何处打井，以求最大化预期效益；美国总统候选人希望确定该把宣传的资金花在何处，以求赢得竞选的可能性最大；,常用的算法设计方法,递归法（Recursion） 分治法(Divide-and Conquer)、 贪心法(Greedy) 动态规划(Dynamic Programming)、 回溯（Backtracking） 分支限界法（Branch and Bound） 近似算法(Approximation),问题求解,理解问题,精确解或近似解 选择数据结构 算法设计策略,设计算法,算法的设计目

4、标,算法应易于理解、编程和调试 算法应尽可能有效地利用计算机的资源，特别地，应尽可能快地运行,好算法的判断标准,1.正确性 2.健壮性 3.时间复杂性 4.空间复杂性 5.可读性 6. 灵活性（Flexibility）、可重用性(Reuseabale)等,算法复杂度分析,算法复杂性,体现在运行该算法所需要的计算机资源多少上 所需资源越多，该算法的复杂性越高 所需资源越少，该算法的复杂性越低,时间复杂性：算法执行需要的时间资源 空间复杂性：算法执行需要的空间资源,百鸡问题,公元5世纪末,我国古代数学家张丘建在他所撰写的算经中，提出了这样的一个问题：“鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一

5、。百钱买百鸡，问鸡翁、母、雏各几何？”,a：公鸡数 b：母鸡数 c：小鸡数 a + b + c = 100 5a + 3b + c/3 = 100 c % 3 = 0,void chicken_question(int n, int ,算法有三重循环 内循环体的执行次数为(n+1)(n+1)(n+1),void chicken_problem(int n, int ,算法有两重循环 内循环体执行次数为(n/5 + 1)(n/3 + 1),货郎担问题,货郎担问题是一个经典问题。某售货员要到若干个城市销售货物，已知各城市之间的距离，要求售货员选择出发的城市及旅行路线，使每一个城市仅经过一次，最后回

6、到原出发城市，而总路程最短。,用图的顶点代表城市，边的权重表示城市间的距离，这个问题可以转化为求一个图的最短哈密顿回路,哈密顿回路可以定义为n1个相邻节点vi0,vin-1,vi0的一个序列 可以通过生成n1个中间城市的组合来得到所有的旅行路线，计算这些路线的长度，然后求得最短的线路,算法时间复杂度 O（n！）,对于所设计的算法，如何说明它是有效的？ 如果对于同一问题，有多个不同的解法，如何知道哪一个算法更有效？ 算法复杂性分析目的在于选择合适的算法和改进算法,实验测量法（实际执行时间、执行指令的条数） 把算法用某种程序设计语言实现并在计算机上运行，计算实际运行时间,如何进行算法时间效率分析,

7、例：让一台更快的、运行插入排序的计算机（计算机A）与一台较慢的、运行合并排序的计算机（计算机B）进行比较。两者都要对一个大小为一百万个数的数组进行排序。假设计算机A每秒能执行10亿条指令，而计算机B每秒只能执行一千万条指令。,计算机A花费的时间： 2*（106）2条指令/109条指令/秒2000秒 计算机B花费的时间： 50*106lg106条指令/107条指令/秒100秒,影响实验测量时间的因素,程序的输入长度 编译程序生成目标代码的质量 计算机指令的质量和速度 算法本身的优劣,实验测量法（实际执行时间、执行指令的条数） 缺点： 必须先运行根据算法编制的的程序；所得的时间统计量依赖于计算机的

8、硬件、软件等环境因素，容易掩盖算法本身的优劣。,事前分析(估计)法 忽略机器性能对运行时间的影响 使用问题输入规模为参数的函数来衡量,算法执行的时间是算法优劣和问题规模的函数。评价一个算法的优劣，可以在相同的规模下，考察算法执行时间的长短来进行判断。,选定输入规模,规模越大，需要的运行时间越长 使用以算法输入规模n为参数的函数T（n）研究算法效率,运行时间的度量单位,找出算法中最重要的操作基本操作，计算它们的运行次数 基本操作通常是算法最内层循环中最费时的操作,例：A是一个由n个不同元素的实数数组，给出求其最大和最小元素的算法和时间复杂性 void MinMax(double A, int n

9、, 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的任何输入的最短运行时间 最坏时间复杂度 算法对具有长度为n的任何输入的最长运行时间 平均时间复杂度 在平均输入下，算法的运行时间。通常假设给定长度的各种输入概率相同。,例:A是一个由n个不同元素的实数数组，给出确定给定实数K是否在A中的算法及其时间复杂性,SequentialSearch(A0n-1,K) i

10、 = 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）,常用最坏运行时间估计,平均运行时间难以计算 假设每一个输入具有相同的概率有时没有意义 平均运行时间常常与最坏运行时间有相同的数量级 实际问题中，算法的运行时间常常达到这个上界,渐近时间复杂性,指当问题规模趋向无穷大时，该算法时间复杂度的数量级,一般说来，当n单调增加且趋于时，T（n）也将单调趋于 对于T（n），如果存在g（n），使得当n 时，有 T

11、（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）简单,几个常见的渐进符号,渐近上界符号O 渐近下界符号 紧渐近界记号符号,渐进符号,渐近上界符号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）的下界由

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

13、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)。,渐近分析记号的运算性质,定理： 若 A（n）=amnm+a1n+a0 是关于n的m次多项式，则 A（n）=（nm） 此定理说明，当要比较的两个算法的渐进复杂性的阶不相同时，只要确定出各自的阶 如f(n) = 20n2 + 5n + 10 g(n) = 3n5 + 2n3 + 100,算法的渐进时间复杂性,算法中基本操作重复执行的次数是问题规模n的某个函数f（n），算法的时间度量记作T（n）= O（ f（n）。它表示随问题规模n

14、的增大，算法执行时间的增长率不会超过f（n），称为算法的渐进时间复杂性，简称时间复杂性。,算法效率分析,非递归算法 递归算法,例：找出n个元素的最大值,MaxElement(A0n-1) maxval = A0 For i = 1 to n-1 do if Ai maxval maxval = Ai return maxval ,n-1 T(n) = 1= n-1 i=1 = O(n),分析非递归算法效率的通用方案,决定用哪个（哪些）参数作为输入规模的度量 找出算法的基本操作 检查基本操作的执行次数是否只依赖输入规模，如果还依赖其他特性则应区分最差、平均及最优效率 建立算法基本操作执行次数的求

15、和公式 对求和公式求解，至少应确定其增长次数,递归算法的分析,一个过程在运行时直接或间接地调用自己，则该过程称为递归程序,例：计算阶乘函数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,int s,int t) /*将xst归并排序为auxst*/ if (s=t) auxs=xs; else m=(s+t)/2; msort(x,aux,s,m); msort(x,aux,m+1,t); merge(aux,x,s,m,t); ,时间复杂度递归公式 T(n) = 2T(n/2) + n (n0) T(1) = 1,T(n) = O(nlogn),分析递归算法效率的通用方案,决定用哪个（哪些）参数作为输入规模的度量 找出算法的基本操作 检查基本操作的执行次数是否只依赖输入规模，如果还依赖其他特性则应区分最差、平均及最优效率 对算法基本操作的执行次数建立一个递推关系式以及相应的初始条件 求解递归关系式，至少确定其增长次数,解递归方程,推测法 递归树 主定理,推测法,T(n) = 4T(n/2) + n T(1) = O(1),推测