百度Pascal吧公开培训教材-Pascal培训课程算法讲义-第一讲
第一讲 算法基础知识
一、算法
算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。
简单的来说，算法，是对一类问题的机械的、统一的求解方法（《苏教版高中数学必修3》（江苏凤凰教育出版社））。
一个算法应该具有以下五个重要的特征：
1、有穷性（Finiteness）：算法的有穷性是指算法必须能在执行有限个步骤之后终止；
2、确切性(Definiteness)：算法的每一步骤必须有确切的定义； 3、输入项(Input)：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件；
4、输出项(Output)：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；
5、可行性(Effectiveness)：算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步，即每个计算步都可以在有限时间内完成（也称之为有效性）。
第1页，共13页
百度Pascal吧公开培训教材-Pascal培训课程算法讲义-第一讲
二、算法的评价
对于算法的评价通常有五个方面。 1、正确性
这一点不用多说，如果说一个算法不正确，那么这个算法就是失败的，是错误的，其他几个方面就无从谈起。事实上，一个算法的正确性必须使用数学手段严格证明，不能使用数学方法证明的算法就不能保证其正确性。
2、可读性（简单性）
这一点主要说明的是算法是否易于被人理解，与其效率无关。例如，选择排序法就比希尔排序法简单，更易于理解，但是效率却不如希尔排序法。
3、容错性（健壮性）
指一个算法对不合理数据输入的反应能力和处理能力。 4、时间复杂性
算法的运行时间指一个算法在计算机上运行所花的时间。大致可以使用计算机执行简单操作所需要的时间与其次数的乘积。
5、空间复杂性
算法在运行过程中临时占用的存储空间的大小被定义为算法的空间复杂性。备注：系统实行递归所使用堆栈也需计算在内。
在OI范围内，在确保正确性的前提下，时间复杂性和空间复杂性是相对最重要的。
第2页，共13页
百度Pascal吧公开培训教材-Pascal培训课程算法讲义-第一讲
三、时间复杂度
在第一卷中，我们已经多次提到了这个名词。现在，我们用科学的方式定义它，并表示它。（这里，我们使用《算法导论》一书的符号与定义）
首先，我们说明，函数T(n)为一个规模为n的问题的运行时间。显然，n∈????+。
然后，我们定义符号Θ。
????(????(????))={????(????)|?????1,????2,????0,?????≥????0
(a>0;b,c<0)，都有T(????)=Θ(????2)。
下面我们试着证明一个结论：对于任何一个T(????)=????????2+????????+???? 其实，我们只要通过定义，求出????1,????2即可。
????1????2≤????????2+????????+????≤????2????2 ????1≤????+?????????1+?????????2≤????2
?0≤????1????(????)≤????(????)≤????2????(????)} 进行代数变形。
只需要将n=1带入即可，至于????2的最小值，需要求一个极限。
总之，????1,????2是存在的。
c2????in=lim(????+?????????1+?????????2)=????
????→∞
由于整个函数是单调减的，我们可以很轻易地求出????1的最大值，
所以原命题为真命题。
当然，这个命题只要a>0就能成立，希望同学们能够自己动手进行证明。
第3页，共13页
百度Pascal吧公开培训教材-Pascal培训课程算法讲义-第一讲
事实上，对于任意多项式函数
????(????)=?????????????????
????=0????
只要保证????????>0且????????为常数，都有
这个希望有兴趣的同学们能够自己证明一下。 下面我们对Θ进行更深入的研讨。 如右图（图来源于《算法导论》），我们可以看到，对于所有n>????0,f(n)在一个常因的一个渐进确界。
Θ(g(n))的定义需要每一个成员f(n)
????(????)=Θ(????)
子范围内与g(n)相等。我们称g(n)为f(n)
∈Θ(g(n))都是渐进非负，也就是说当n足够大时f(n)是非负值（渐进正函数则是当n足够大时总为正值）。这就要求函数g(n)本身也必须是渐进非负的，否则集合Θ(g(n))就是空集，因此，假定Θ记号中用到的每个函数都是渐进非负的。这个假设对于本章中定义的其他渐进记号也是成立的。
Θ(1)表示常函数。
下面我们定义一下渐进上界(O)和渐进下界(Ω)。 O(????(????))={????(????)|?????,????0,?????≥????0?0≤????(????)≤????????(????)} 这里备注一下，在一些文献中，O记号会非正式的表示Θ记号。
第4页，共13页
Ω(????(????))={????(????)|?????,????0,?????≥????0?0≤????????(????)≤????(????)} 百度Pascal吧公开培训教材-Pascal培训课程算法讲义-第一讲
为表示函数f(n)为集合O(g(n))的一个元素，记f(n)=O(g(n))。注意f(n)=Θ(g(n))已经隐含了f(n)=O(g(n))，因为Θ记号强于O记号，按照集合论的写法，有Θ(g(n))∈O(g(n))。由此可以看到，
对于二次函数f(n)= ????????2+????????+????(a>=0)都有f(n)=O(????2)
这里说明一下，任意一个线性函数
f(n)=an+b也在O(????2)中。这个同学们可以自行证明。
三个渐进函数之间有一个关系。
定理：对于任意两个函数f(n)和g(n)，f(n)= Θ(g(n))当且仅当f(n)=O(g(n))且f(n)= Ω(g(n))。 这个希望同学们自行证明。
接下来我们再定义两个符号o记号和ω记号。
O记号所提供的渐进上界可能也可能不是渐进紧确的。例如，界2n2=O(n2)是渐进紧确的，但2n=O(n2)不是。我们使用o记号来表示非渐进紧确的上届。
????(????(????))={????(????)|?????,?????0,?????≥????0?0≤????(????)≤????????(????)} ????(????)=0 lim
????→∞????(????)所以我们可以看到，当f(n)=o(g(n))，有
在一些书中，也将上式作为o记号定义。值得注意的是，这些函
第5页，共13页