计算机算法设计与分析（绪论）.ppt

计算机算法设计与分析
程欣宇
考核方式
出勤率
平时作业
解题报告
(90分以上需申请答辩)
本科是考查科目,不笔试,不补考
总成绩= 解题报告分数- (缺课+缺作业次数)x 5
解题报告要求
注明在北大或浙大等ACM在线测评系统注册的账号、题目号、提交号(含失败)及提交时间。
5页以上ppt,20分
阐释清楚问题描述和解题思路,20分
实用图、表、公式、实例、动画等方式清楚描述,20分
具有多种改进方法对比,20分
附源代码(含注释),10分
答辩分,10分
主要章节
Chapter 1
Chapter 2
Chapter 3
Chapter 4
Chapter 5
算法概述
递归与分治
动态规划
贪心算法
回溯算法
第一章算法概述
为什么要学习算法?
算法是计算机科学的灵魂!
图形图像有图像处理、图像生成的算法。
操作系统有计算机资源调度的算法。
人工智能有机器学习、机器分类、机器推理的算法。
大型数据库系统也包含了众多的数据存储、数据检索的算法。
数据结构这门课也介绍了常用和经典的存储、搜索、排序的算法。
本门课从更通用的角度,介绍算法的设计思路、优化思路、以及算法好坏的评估方法。
第一章算法概述
学好了算法有哪些好处?
帮助理解和评价其它课程的算法;
对做研究有很大帮助;
对软件开发有很好的帮助:
很多国际大公司招聘人员,只考算法题,不考具体某个开发工具的熟练程度。
即便做一个小项目,掌握好算法也能比没学习过算法的同行或者外行能够拿出更多好的解决方案,以使软件项目中在运行速度上瓶颈能够得到更好解决。
能够精炼的抽象所碰到的问题,用学习到的方法轻松解决。
对解决生活、工作中一些问题有帮助,我们的ACM/ICPC题目绝大多数是非常实际的生产、生活问题。
第一章算法概述
算法与程序
满足以下性质的程序,称为算法
有零个或多个外部的输入
至少有一个输出
每条指令是清晰的、无歧义的
每条指令的执行次数、执行时间是有限的
算法复杂度
定义:运行一个算法所需要的计算机资源的量。
分类:时间复杂度、空间复杂度
符号:N、I、A、T、S均是单词首字母
严格的时间复杂度的定义
我们常考虑三种情况
渐近意义下的复杂度
在理论上,我们比较两个一个算法的复杂度,只比较问题规模增长它们的增长趋势,而不比较具体的数值大小,因此,引入了渐进意义下的复杂度。
定义:如果存在T(N),使得当N趋近∞时,(T(N)-T(N))/T(N)→0,那么,就说T(N)是T(N)当N →∞时的渐近态,也称T(N)是算法A当N →∞时的渐近复杂度。
例:T(N)=3N2+4N LogN +7 和 T(N)=3N2
~
~
~
~
N
T
T(N)
T(N)
~
~
渐近意义下的阶–上界O
设函数f(N)和g(N)是正数集上的正函数。
如果存在正的常数C和自然数N0,使得当N≥N0时,有f(N)≤g(N),则称f(N)的一个上界是g(N),记为
f(N)=O(g(N))。
例子:
当N≥1时, 有3N ≤4N, 所以3N=O(4N);
当N≥1时, 有N+1024≤1025N, 所以N+1024=O(1025N);
当N≥10时,有2N2+11N-10≤3N2,所以2N2+11N-10 =O(3N2);
当N≥1时, 有N2≤N3, 所以N2=O(N3);
反例:
(5) 无法找到C和N0使得,N3=O(N2),证明,若存在常数C和自然数N0,使得当N ≥N0时,2成立,则N ≤C,而C是常数,N可以一直增大超过C,存在矛盾,无法成立。