第一节 算法概述

算法是什么？

  算法是软件工程非常重要的基础科目。简单来说，算法就是解决特定问题的方法和步骤。为了解决现实生活中的各种问题，我们就把现实问题对应成数学问题，然后设计公式，编写程序，让计算机编译，运行得到答案——这时候运用的方法就是算法。

  尽管这里运用了“公式”这个词来形容算法，然而算法并不是大家印象中死板的数学公式。因为计算机能够执行复杂的计算，所以公式可以设计成好几行，甚至几百行，用到很多数学理论。因此，就算学习过算法的人，也不一定会设计算法。因为数学、程序上面的东西都比较复杂。想要把现实中的问题对应到数学问题，那就更加复杂了。

  通常，算法具有由三部分组成：输入、输出、计算过程。说到这里，大家可能会联想到函数。

  输入、输出是一个或一组数据，实际上是将这些数字放在数据结构中比如数组、链表。输入的来源，通常是硬盘中存储的数据，或者是由键盘输入的数字；输出的去处可能是硬盘中的文件或是由硬盘中的数据转换之后以其他的形式呈现，例如显示器。

  计算过程是一连串处理数字的指令。指令有两种类型，一种是运算，例如数学运算的加减乘除、逻辑预算的与或非、比较大小、位运算等等；另一种则是读写，例如读取某处的数字，存储数字至某处。

  在算法之前的定义中，算法的计算步骤必须是有限的。用程序的语言说：算法不能无限轮回。之所以规定算法的步骤有限是为了方便统计计算的步数。但是事实上，很多的计算机程序都是开启之后保持运行的状态，直到遇到死机或者关机。例如用于网络传输的算法。因此，实际上，算法是可以有无限步的。

计算机只会算数字

  计算机就是一台用于计算的机器，它只会计算、判断以及存储数据，但是能够做得又快又准。而程序，是一连串计算、判断、存储数据的过程。

  计算机只会处理二进制数字，计算机中的每一个文字、每一种颜色、每一种声音，都有它所对应的数字。例，我们规定：用1代表数字“一”，用2代表汉字“乙”，用3代表汉字“人”…一个数字对应一个汉子。按照这样的规定，计算机中所有的汉字都变成了数字。同理，呈现在电脑屏幕上的不同颜色、图片、影像等，都可以转化成数字。一切事物在计算机里都是数字。

  如果我们想要利用计算机解决实际问题，通常要考虑两个方面：一、计算机应该使用哪些设备?计算机如何操作这些设备？二、显示问题如何对应到数学问题?如何设计算法？当然，编写程序，计算数字，这就是程序设计师的工作。

数学和程序这么复杂，为什么要用计算机解决现实问题？

  计算机解决问题的速度很快，一秒可以进行几千万次以上的计算。即使是很大的数据量，计算机也能够轻松解决。打开计算机中的一份文件，用鼠标滑动页面。眼镜还没来得及眨一下，正确的内容就已经显示在显示器上了。事实上，在我们滑动页面的时候，计算机已经完成了很多次的计算，然后把正确的内容展示在显示器上了。

  人们想要用计算机来解决问题，就是因为它速度快，正确率高，而且计算机会按照人们设计的程序来进行运算。程序设计师只要设计好一个好的程序，接下来的工作就可以让计算机代劳了。计算机的运算速度比人要更快更好，计算机做得到人类做不到是事。相比于算法的复杂，程序和计算机的组合能够给人们带来更多的便利。现在，计算机应用在人们生产生活的各个方面，程序设计师们设计的程序也在世界各地发光发热。

如何表示一个算法

  有人用伪代码来表示一个算法。如要实际计算机程序，伪代码是比较方便使用的。下面是一段伪代码：

1
2
3
4
5
6
7
GREATEST_COMMON_DIVISOR(a, b)
    while a ≠ b do
        if a > b then
            a ← a - b
        else
            b ← b - a
    return a

  当然，你也可以使用流程图来表示一个算法。下面是一个流程图：
流程图

如何实现一个算法

  实现的意思就是实际操作，实际运行。对于程序设计师来说，就是把算法写成程序，比如C/C++程序或者是java程序，然后在计算机上去执行。这个是我们接下来我们主要研究的东西。

衡量算法优良的标准

  要评价一个算法的好坏，最基本的两个指标就是时间复杂度和空间复杂度。用直观的感觉来说，就是程序的执行时间和内存使用量。但是由于不同的计算机执行时间会有所不同，而且这两项指标同时会受到程序语言的类型、程序设计的技巧的影响。因此，执行时间和内存使用量并不是一个稳定的评判标准。

1
2
3
4
for ( i = 0 ; i < length(A) ; i ++ )       
    for (j = 0 ; j < length(A)-I ; j ++ )  
        if A [ j ] < A [ j+1]         
            swap A [ j ] and A [ j+1 ]

  上面的程序是一个简单的数组排序问题，我们经常采用统计计算步骤的方法来去衡量一个算法的时间复杂度。

1
2
3
4
5
6
7
  Code                                                 step
for ( i = 0 ; i < length(A) ; i ++ )                  n         
    for (j = 0 ; j < length(A)-I ; j ++ )          n ( n - 1) / 2 
        if A [ j ] < A [ j+1] {                    n ( n - 1) / 2 
            Temp = A [ j ] ;                       n ( n - 1) / 2 
            A [ j ] = A [ j + 1 ] ;                n ( n - 1) / 2 
            A [ j + 1 ] = temp ;                   n ( n - 1) / 2

Sum = n + 5n ( n – 1 ) / 2
= n + 2.5n2 – 2.5n
= 2.5n2 – 1.5n
= O ( n2 )

  像上面那个算法，我们称它的时间复杂度为O ( n2 )。这是因为在上式中，我们进行的并不是精确的步骤计算。针对不同的数据，系数变动会很大。因此，我们只取代数式的最高次方。最高次方越大，时间复杂度越高，算法的速度也就越慢。并且，我们规定n必须足够大。尽管这样的估算并不是非常精准，但是还是可以对一些常见的算法进行简易的分类，粗略地比较快慢。

  下面是几种常见算法的时间复杂度和空间复杂度。（空间复杂度的计算和时间复杂度类似。）

1
2
3
4
5
6
7
type                           time              space
bubble sort ( 冒泡排序 )      O ( n2 )           O ( n ) 
insertion sort ( 插入排序 )   O ( n2 )           O ( n )  
merge sort ( 归并排序 )       O ( n log ( n ) )  O ( n )  
quicksort ( 快速排序 )        O ( n2 )           O ( n )  
heapsort ( 堆排序 )           O ( n log ( n ) )  O ( n )  
counting sort ( 计数排序 )    O ( n + r )        O ( n + r )

学习编程语言

  学习编程语言，有两个层次：一是语言本身的语法，二是把算法转换成代码的能力。算法固然重要，然而更重要的是用一种语言来把它表述出来，这样它才能发挥作用。而使用编程语言将算法描述出来这个过程，正是我们今后学习的重点。关于各种编程语言，本教程不作详细介绍，因为其他的书籍已经介绍得足够详细了。接下来对算法的描述，以C/C++语言为主，部分辅以java语言。

参考书目：

1.《算法竞赛入门经典（第二版）》 （刘汝佳编著，2009年，清华大学出版社）
2.《数据结构实用教程（C语言版）（第二版）》（2009年，清华大学出版社）