文档介绍：计算机算法设计与分析(第2版)
王晓东编著
电子工业出版社
第1章算法概述
学习要点:
理解算法的概念。
理解什么是程序,程序与算法的区别和内在联系。
掌握算法的计算复杂性概念。
掌握算法渐近复杂性的数学表述。
掌握用C++语言描述算法的方法。
算法(Algorithm)
算法是指解决问题的一种方法或一个过程。
算法是若干指令的有穷序列,满足性质:
(1)输入:有外部提供的量作为算法的输入。
(2)输出:算法产生至少一个量作为输出。
(3)确定性:组成算法的每条指令是清晰,无歧义的。
(4)有限性:算法中每条指令的执行次数是有限的,执行每条指令的时间也是有限的。
程序(Program)
程序是算法用某种程序设计语言的具体实现。
程序可以不满足算法的性质(4)。
例如操作系统,是一个在无限循环中执行的程序,因而不是一个算法。
操作系统的各种任务可看成是单独的问题,每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。
问题求解(Problem Solving)
证明正确性
分析算法
设计程序
理解问题
精确解或近似解
选择数据结构
算法设计策略
设计算法
算法复杂性分析
算法复杂性= 算法所需要的计算机资源
算法的时间复杂性T(n);
算法的空间复杂性S(n)。
其中n是问题的规模(输入大小)。
算法的时间复杂性
(1)最坏情况下的时间复杂性
Tmax(n) = max{ T(I) | size(I)=n }
(2)最好情况下的时间复杂性
Tmin(n) = min{ T(I) | size(I)=n }
(3)平均情况下的时间复杂性
Tavg(n) =
其中I是问题的规模为n的实例,p(I)是实例I出现的概率。
算法渐近复杂性
T(n) , as n;
(T(n) - t(n) )/ T(n) 0 ,as n;
t(n)是T(n)的渐近性态,为算法的渐近复杂性。
在数学上, t(n)是T(n)的渐近表达式,是T(n)略去低阶项留下的主项。它比T(n) 简单。
渐近分析的记号
在下面的讨论中,对所有n,f(n) 0,g(n) 0。
(1)渐近上界记号O
O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n n0有:0 f(n) cg(n) }
(2)渐近下界记号
(g(n)) = { f(n) | 存在正常数c和n0使得对所有n n0有:0 cg(n) f(n) }