算法概述算法概述.pptVIP

算法分析与设计 杨秋妹 yqmbegonia@163.com 教材：《计算机算法设计与分析》 王晓东 编著 电子工业出版社 出版 参考教材 严蔚敏等著，《数据结构》，清华大学出版社 Thomas H.Cormen等著《算法导论》，机械工业出版社 成绩 期末考试：70% 期中考试：无 平时成绩：30% 考勤 实验 综合性实验 在线做题 / / 教学目的 教学目的 培养良好的程序设计习惯和风格 学习常用的、有代表性的算法 培养分析算法时间和空间复杂度的初步能力 程序=数据结构+算法 乘汽车旅行的人总希望找出到目的地的尽可能的短的行程。如果有一张地图并在图上标出每对十字路口之间的距离，如何找出这一最短行程？ 建立解题模型——数据结构 解决方法——算法 什么是算法 算法是一系列的计算步骤，用来将输入数据转换成输出结果。 算法是一个有穷的解决问题的指令序列。每条指令都必须有清楚的含义并且在有穷长的时间内用有穷的动作完成。 一个算法无论接受任何输入，都必须在有穷步内停止。 排序问题 输入：由n个数构成的一个序列a1,a2,…,an 输出：对输入序列的一个排列（重排）a1’,a2’,…,an’，使得a1’=a2’=…=an’ 算法：插入排序，冒泡排序，快速排序，合并排序等 算法是用来解决一类计算问题的，注意是一类问题，而不是一个特定的问题。 例如，一个排序算法应该能对任意一组数据进行排序，而不是仅对int a[] = { 1, 3, 4, 2, 6, 5 }; 算法的描述 自然语言； 程序设计语言； 类程序语言 选择排序算法的自然语言描述 排序过程 首先通过n-1次关键字比较，从n个记录中找出关键字最小的记录，将它与第一个记录交换 再通过n-2次比较，从剩余的n-1个记录中找出关键字次小的记录，将它与第二个记录交换 重复上述操作，共进行n-1趟排序后，排序结束 选择排序算法的C语言描述 算法的几个特性 算法是指解决问题的一种方法或一个过程。 满足性质： (1)输入：有零个或多个外部提供的量作为算法的输入。 (2)输出：算法产生至少一个量作为输出。 (3)确定性：组成算法的每条指令是清晰，无歧义的。 (4)有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。 什么是程序 程序是算法用某种程序设计语言的具体实现 程序可以不满足算法的有穷性 算法可以解决的问题 因特网——快速地访问和检索大量的信息 有哪些信誉好的足球投注网站引擎三段式工作流程 搜集 批量搜集，增量式搜集；搜集目标，搜集策略 预处理 关键词提取；重复网页消除；链接分析； 服务 查询方式和匹配；结果排序；文档摘要 算法可以解决的问题 电子商务——保持信用卡号、密码、银行结单等信息的私密性，公共密钥加密技术和数字签名技术 算法可以解决的问题 制造业和其他商业应用中，是否能最有效地分配稀有资源，例如，石油公司确定在何处打井，以求最大化预期效益；美国总统候选人希望确定该把宣传的资金花在何处，以求赢得竞选的可能性最大； 常用的基础算法 递归法（Recursion） 分治法(Divide-and Conquer)、 贪心法(Greedy) 动态规划(Dynamic Programming)、 回溯（Backtracking） 分支限界法（Branch and Bound） 近似算法(Approximation) 问题求解 算法的设计目标 算法应易于理解、编程和调试 算法应尽可能有效地利用计算机的资源，特别地，应尽可能快地运行 好算法的判断标准 1.正确性 2.健壮性 3.时间复杂性 4.空间复杂性 5.可读性 6. 灵活性（Flexibility）、可重用性(Reuseabale)等 算法复杂度分析 算法复杂性 体现在运行该算法所需要的计算机资源多少上 所需资源越多，该算法的复杂性越高 所需资源越少，该算法的复杂性越低 时间复杂性：算法执行需要的时间资源 空间复杂性：算法执行需要的空间资源 如何进行算法时间复杂性分析 ⑴实验测量法（实际执行时间、执行指令的条数） 把算法用某种程序设计语言实现并在计算机上运行，计算实际运行时间 例：让一台更快的、运行插入排序的计算机（计算机A）与一台较慢的、运行合并排序的计算机（计算机B）进行比较。两者都要对一个大小为一百万个数的数组进行排序。假设计算机A每秒能执行10亿条指令，而计算机B每秒只能执行一千万条指令。 计算机A花费的时间： （106）2条指令/109条指令/秒＝1000秒 计算机B花费的时间： 106lg106条指令/107条指令/秒≈2秒 影响实验测量时间的因素 程序的输入长度 编译程序生成目标代码的质量 计算机指令的质量和速度 算法本身的优劣 ⑴实验测量法（实际执行时间、执行指令的条数） 缺点： 必须先运行根据算法编制的的程序；所得的