学习目标

  1. 掌握与计算机算法相关的各个名词、术语的含义
  2. 了解时间复杂度和空间复杂度的基本概念
  3. 理解计算机算法的5个重要特征
  4. 了解计算机算法涉及的5个基本内容
  5. 掌握计算机频率计数和估算算法时间复杂度的基本方法

算法的基本概念

只能笼统的将算法定义为解决某个确定问题的一种特殊的方法。若对算法做稍许详细一些的非形式化描述,那么算法就是一组有穷的规则,它规定了解决某一特定类型问题的一系列计算方法!

算法的重要特性

  1. 确定性

    算法的每一种运算都必须要有明确的定义,每一种运算应该执行怎样的动作必须是清楚地,即没有二义性的!

    例如算法中不允许有”将1或2与某个确定的数相加”之类的运算

  2. 能行性

    一个算法能行指的是算法中有待实现的运算都是基本的运算,即每种运算至少原理上可以由人用纸和笔在有限时间内完成。

    整数运算时能行性的一个例子,而实数运算不行,因为实数可能有无限长!

  3. 输入

    每个算法有0个或多个输入,是在算法开始之前给定的,取自特定的对象集合!

  4. 输出

    每个算法产生一个或多个输出,这些输出是同输入有某种特定关系的量!

  5. 有限性

    任何一个算法总在执行有限步的运算之后就停止执行,仅仅满足前面4条特性的一组规则称之为计算过程,不能称之为算法,例如操作操作系统!

    不能把任何在有限步内就停机的算法投入计算机中运行,而只能把那些在相当有限步内停机的算法投入计算机中运行。总而言之,应尽可能避免无益耗费计算机的宝贵资源

算法的基本内容

为了制定一个算法,一般需要经过设计、确认、分析、编码、检查、调试、计时等阶段

  1. 设计算法:使读者学会已经被实践证明的有用的一些基本设计策略

  2. 表示算法:基本采用结构程序设计的方式将设计的算法表示出来

  3. 确认算法(Algorithm Validation)(确认算法 = 设计正确 + 程序证明)

    算法确认:设计出一个算法以后,就应证明它对于所有可能合法的输入都可以给出正确的答案。

    确认的目的在于使我们确信这个算法将可以正确无误的工作,而与所采用的程序设计语言无关!

    程序证明:在将程序投入到计算机上执行以前,实际上还应该证明该程序是正确的,也就是证明该程序对于所有可能的合法输入都能得到正确的结果。

  4. 分析算法(Algorithm Analysis)

    算法分析:对于每个算法需要多少时间和存储空间作定量分析。

    作用:可以预计所设计的算法可以在怎样的环境中有效的执行,可以知道在最好、最坏及平均情况下执行得怎样,还可以使读者对于解决同一问题的不同算法执行的有效性作出比较判断

  5. 测试程序(测试程序 = 调试程序 + 作时空分布图)

    调试程序:在抽象数据集上执行程序,以确定是否会产生错误的结果,如果产生错误的结果,就修改源程序

    局限性:调试只能指出有错误,而不能指出程序不存在错误。

    作时空分布图:首先使用各种给定的数据执行调试认为是正确的程序,然后测定为计算出正确的结果所花的时间和空间,以印证以前所做的分析是否正确和支出实现最优化的有效逻辑位置。


算法分析

计算时间的渐进表示

常用的整数求和公式

以下公式i的取值范围都是从1到n

$$
\sum_{i=1}^n{i} = n(n + 1) / 2 = \theta(n^2)
$$

$$
\sum_{i=1}^n{(i^2)} = n(n + 1)(2n + 1) / 6 = \theta(n^3)
$$

$$
\sum_{i=1}^n{i^k} = n^{(k+1)}/(k+1) + n^k/2 + 低次项 = \theta(n^{(k+1)})
$$

作时空性能分布图

事后测试是在对算法进行了设计、确认、事前分析、编码及调试以后所要做的工作,以确定程序所耗费的精确时间和空间,也就是作时空性能分布图。事后测试与所使用的数字计算机密切相关!

关于噪声

注意:如果在一台时钟精确度不高的计算机上运行耗时很小的程序,那么所得到的计时图只不过是一些”噪声”,这样,时间分布性能将会完全淹没在”噪声”中。

解决方案
  1. 增加输入规模,直至得到算法所需的可靠的时间总量
  2. 取足够大的r,将该算法重复执行r次,然后用总时间除以r次

如何作出时间性能分布图

  1. 对于事前分析为θ(g(n))(意思就是有限个对n的不同取值带入g(n)求和之后, g(n)既是这个和的上界,也是这个和的下届)计算时间的算法,应该按照输入不断增大其规模的数据集,再利用这些数据集在数字计算机上运行程序,从而得到算法消耗的时间,进而画出这一数量级的时间曲线,倘若这条曲线和事前分析的曲线形状吻合,那么就印证了事前分析的结论!

    注意:

    1. O是上界符号,存在正常量c和n0,使得对所有n≥n0,有0≤f(n)≤cg(n)
    2. Ω是下界符号,存在正常量c和n0,使得对所有n≥n0,有0≤cg(n)≤f(n)
    3. Θ是同阶记号,存在正常量c1、c2和n0,使得对所有n≥n0,有c1 g(n)≤f(n)≤c2 g(n)
    4. o是低阶记号,对任意正常量c>0,存在常量n0>0,使得对所有n≥n0,有0≤f(n)<cg(n)
  2. 对于事前分析为O(g(n))(公式为g(n)的表达式)计算时间的算法,就应该首先在各种数据集规模的范围内分别按照最好情况,最坏情况以及平均情况的数据集独立运行程序,然后做出各种情况的时间曲线,进而根据这些曲线来分析最优的有效逻辑位置。

注意:如果为了解决某一问题,分别设计了多种具有同一数量级的不同算法,或者为了加快某种算法的速度,在同一数量级情况下做了一些改进,那么,只要在输入相同数据集的情况下作出它们的时间分布图就可以比较出哪一个算法的运行效率高一些!


最优算法概述

在最优算法中,没有考虑空间复杂度,主要原因在于,只要是在一个合理的范围内使用空间,则对于时间的考虑应该比对于空间的考虑更加重要

  1. 对于同一个求解问题,存在两个不同算法,在上述意义下都是最优的,那么如果要确定这两个算法中哪一个是真正最优的,就必须进一步对这两个算法的时间复杂度表达式中的高阶项常数因子进行进一步的比较。一般说来,常数因子小的算法要优于常数因子大的算法!
  2. 另一方面要注意关于时间复杂度渐进阶的确定,与数据规模n及常数因子c的选取有关,当数据规模小时,时间复杂度阶低的算法不一定比时间复杂度阶高的算法更有效!