算法复杂性分析算法概述.pptVIP

算法概述 杨秋妹 yqmbegonia@163.com 程序=数据结构+算法 乘汽车旅行的人总希望找出到目的地的尽可能的短的行程。如果有一张地图并在图上标出每对十字路口之间的距离，如何找出这一最短行程？ 建立解题模型——数据结构 解决方法 什么是算法 算法是一个有穷的解决问题的指令序列。每条指令都必须有清楚的含义并且在有穷长的时间内用有穷的动作完成。 一个算法无论接受任何输入，都必须在有穷步内停止。 排序问题 输入：由n个数构成的一个序列a1,a2,…,an 输出：对输入序列的一个排列（重排）a1’,a2’,…,an’，使得a1’=a2’=…=an’ 算法：插入排序，冒泡排序，快速排序，合并排序等 算法的几个特性 算法是指解决问题的一种方法或一个过程。 满足性质： (1)输入：有零个或多个外部提供的量作为算法的输入。 (2)输出：算法产生至少一个量作为输出。 (3)确定性：组成算法的每条指令是清晰，无歧义的。 (4)有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。 什么是程序 程序是算法用某种程序设计语言的具体实现 程序可以不满足算法的有穷性 算法的描述 自然语言； 程序设计语言； 类程序语言 算法可以解决的问题 人类基因的目标是找出人类DNA的所有十万种基因，确定构成人类DNA的30亿种化学基对的各种序列，将这些信息存储在数据库中，并开发出用于进行这方面数据分析的工具。 因特网——快速地访问和检索大量的信息 电子商务——保持信用卡号、密码、银行结单等信息的私密性，公共密钥加密技术和数字签名技术 制造业和其他商业应用中，是否能最有效地分配稀有资源，例如，石油公司确定在何处打井，以求最大化预期效益；美国总统候选人希望确定该把宣传的资金花在何处，以求赢得竞选的可能性最大； 常用的算法设计方法 递归法（Recursion） 分治法(Divide-and Conquer)、 贪心法(Greedy) 动态规划(Dynamic Programming)、 回溯（Backtracking） 分支限界法（Branch and Bound） 近似算法(Approximation) 问题求解 算法的设计目标 算法应易于理解、编程和调试 算法应尽可能有效地利用计算机的资源，特别地，应尽可能快地运行 好算法的判断标准 1.正确性 2.健壮性 3.时间复杂性 4.空间复杂性 5.可读性 6. 灵活性（Flexibility）、可重用性(Reuseabale)等 算法复杂度分析 算法复杂性 体现在运行该算法所需要的计算机资源多少上 所需资源越多，该算法的复杂性越高 所需资源越少，该算法的复杂性越低 时间复杂性：算法执行需要的时间资源 空间复杂性：算法执行需要的空间资源 百鸡问题 公元5世纪末,我国古代数学家张丘建在他所撰写的《算经》中，提出了这样的一个问题：“鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一。百钱买百鸡，问鸡翁、母、雏各几何？” a：公鸡数 b：母鸡数 c：小鸡数 a + b + c = 100 5a + 3b + c/3 = 100 c % 3 = 0 算法有三重循环 内循环体的执行次数为(n+1)(n+1)(n+1) 算法有两重循环 内循环体执行次数为(n/5 + 1)(n/3 + 1) 货郎担问题 货郎担问题是一个经典问题。某售货员要到若干个城市销售货物，已知各城市之间的距离，要求售货员选择出发的城市及旅行路线，使每一个城市仅经过一次，最后回到原出发城市，而总路程最短。 用图的顶点代表城市，边的权重表示城市间的距离，这个问题可以转化为求一个图的最短哈密顿回路 哈密顿回路可以定义为n＋1个相邻节点vi0,…,vin-1,vi0的一个序列 可以通过生成n－1个中间城市的组合来得到所有的旅行路线，计算这些路线的长度，然后求得最短的线路 对于所设计的算法，如何说明它是有效的？ 如果对于同一问题，有多个不同的解法，如何知道哪一个算法更有效？ 算法复杂性分析目的在于选择合适的算法和改进算法 如何进行算法时间效率分析 ⑴实验测量法（实际执行时间、执行指令的条数） 把算法用某种程序设计语言实现并在计算机上运行，计算实际运行时间 例：让一台更快的、运行插入排序的计算机（计算机A）与一台较慢的、运行合并排序的计算机（计算机B）进行比较。两者都要对一个大小为一百万个数的数组进行排序。假设计算机A每秒能执行10亿条指令，而计算机B每秒只能执行一千万条指令。 计算机A花费的时间： 2*（106）2条指令/109条指令/秒＝2000秒 计算机B花费的时间： 50*106lg106条指令/107条指令/秒＝100秒 影响实验测量时间的因素 程序的输入长度 编译程序生成目标代码的质量 计算机指令的质量和速度 算法本身的优劣 ⑴实验测量法（