1.2　算法基础

许多初学者认为，学习编程就是学习新的编程语言、技术和框架，其实计算机算法更重要。从C语言、C++、Java、C#到Python，虽然编程语言种类繁多，但经典的算法却是万变不离其宗。所以，练好算法这门“内功”，再结合新技术这些“招式”，才能真正地成为一名合格的程序员。

1.2.1　算法的定义

算法是一组完成任务的指令，因此有计算机工作者这样定义：为了解决某个或某类问题，需要把指令表示成一定的操作序列，操作序列包括一组操作，每个操作都完成特定的功能。简单来说，算法是解决特定问题的步骤描述，即处理问题的策略。

首先来看一个例子—经典问题“百钱买百鸡”。用一百钱买一百只鸡，鸡的品种有公鸡、母鸡和雏鸡，价格分别是：一只公鸡5钱，一只母鸡3钱，三只雏鸡1钱。要求每个品种的鸡至少买一只，问怎样买才能用一百钱买一百只鸡。

整理题干信息，可以得出以下两个限制性条件：

（1）买的公鸡、母鸡、雏鸡的总数量是100只，如图1.2所示。

（2）花的钱数是100钱，根据不同类型的鸡价格不同，可以有如图1.3所示的式子。

算法解析如下：

（1）根据条件2，计算每一种鸡最多能买多少只。

①如果尽可能多地购买公鸡，那么公鸡的购买范围是1～19只，不能超过20只。因为，如果购买20只公鸡，就需要花费100钱（20*5=100），这样无法购买母鸡和雏鸡，不符合题意。

②如果尽可能多地购买母鸡，那么母鸡的购买范围是1～32只，不能为33只，否则需要花99钱（3*33=99），公鸡和雏鸡就没有办法购买了。

③ 3只雏鸡需要花1钱，所以要买雏鸡，就得一起买3只雏鸡，因此雏鸡的数量应为3的倍数，故递增的步长可以设为3。同理，如果尽可能多地购买雏鸡，雏鸡的购买范围应为3～99只。

（2）使用某种编程语言，在公鸡、母鸡、雏鸡的可购买数量范围内列出三重循环，进行穷举，使两个代数式均成立，则为百钱买百鸡的解。

下面来看一下如何使用Python语言实现百钱买百鸡问题的求解。

【实例1.1】 百钱买百鸡。 （实例位置：资源包\Code\01\01）

具体代码如下：

运行结果如图1.4所示。可见，有3种购买方法：4公鸡+18母鸡+78雏鸡；8公鸡+11母鸡+81雏鸡；12公鸡+4母鸡+84雏鸡。

实例1.1中的算法解析思路和Python代码实现，整个过程就是算法的实现过程。

1.2.2　算法的特性

算法主要用于解决“做什么”和“怎么做”的问题，因为解决问题的步骤需要在有限时间内完成，而且解决问题可能有不止一种方法，所以在进行算法分析时最为核心的考察要点是算法的速度。另外，操作步骤中不可以有不明确的语句，使得步骤无法继续进行下去。

总之，一个算法必须满足有输入、有输出、确定性、有限性、有效性五大特性，如图1.5所示。

1．有输入

一个程序中，算法和数据是相互关联的。算法中需要输入数据的值，例如：

注意，输入可以是多个，也可以是零个。零个输入并不代表这个算法没有输入，而是这个输入没有直观地显现出来，隐藏在了算法本身中。

2．有输出

一个算法，需要输出一定的结果，没有输出的算法是没有意义的。有的算法输出的是数值，有的输出是图形，有的输出并不是那么显而易见。例如：

上述3行代码的输出结果如下：

3．确定性

算法中，每条指令及每个步骤的表述都应该是明确的，使计算机能“听懂”，并能照着做，不能存在任何的歧义和模糊性。

日常生活中，我们经常会遇到一些含义不明确的语句。当然，人脑可以根据常识、语境等，自动补充信息使其明确，但即便如此，仍然有可能理解错误（见图1.6）。计算机不比人脑，它只会严格按照指令一步步地执行，无法处理有歧义或表述不明的情况，更不会根据算法的意义来揣测每个步骤的意思，所以算法的每一步都必须给出确定的信息和指令。

4．有限性

一个算法，如果在执行有限步骤后能够实现，或者在有限时间内能够完成，就称该算法具有有限性。例如，在“百钱买百鸡”代码的for循环中，(1,20)、(1,33)、(3,99,3)这几个范围保证了程序的有限性。如果没有此条件，for循环就会无终止地进行，程序也就进入了死循环。

有的算法在理论上满足有限性要求，即可在有限的步骤后完成，但实际上计算机可能会执行一天、一年、十年等。算法的核心就是速度，过慢的算法实际上是没有什么意义的。当然，有些算法非常复杂，确实需要较长的运算时间。但就普通开发而言，快捷、高效是核心，也是进行算法设计时的关键考量要素。

5．有效性

算法的有效性是指每个步骤都必须有效地执行，得到确定的结果，且能方便地用来解决一类问题。如下代码中的“z=x/y;”就是一个无效语句，因为0不可以做分母。

1.2.3　算法的性能分析与度量

算法是解决问题的方法，但解决问题的方法通常不止一个，方法多了，自然而然地就有了优劣之分。这就好比，一个人扫地时，人们往往只会关注扫地任务是否完成；然而当有两三个人同时扫地时，人们就有了比较，可以根据某个评定标准判断谁扫的更好。比如，有人认为A好，因为他扫的快；有人认为B好，因为他扫的干净，等等。

那么，算法的优劣该怎样评定呢？可以从算法的性能指标和算法效率等方面来衡量。

1．算法的性能指标

评定一个算法的优劣，主要有以下几个指标。

（1）正确性。一个算法必须正确，即能解决提出的问题，才有实际的价值。正确性是考量算法时最重要的指标，编程人员应用合适的算法语言实现正确的功能。

（2）友好性。算法实现的功能最终是要给用户使用的，自然要考虑用户的使用习惯，使其具有良好的使用性，人们愿意用，且用着方便。

（3）可读性。一个算法，在其诞生和使用过程中可能会进行多人、多次的修改，也可能会被移植到其他功能中去，因此算法应当是可读的（代码易于理解），以方便程序员对其分析、修改和移植。

（4）健壮性。算法的实际应用中，有时会出现不合理的数据输入或非法操作，因此算法必须具有一定的健壮性，能够对这些问题进行检查和纠正。读者在刚开始学习算法时，可以忽略健壮性的存在，但在后续的开发中，一定要努力让自己的算法具有一定的健壮性。

（5）效率。算法的效率主要指执行算法时对计算机资源的消耗程度，包括对计算机内存的消耗和对计算机运行时间的消耗，两者统称为时空效率。一个算法只有正确性而无效率，是没有意义的，因此也经常把效率用作评定算法是否正确的指标。如果一个算法需要执行几年，甚至几百年，那么无疑这个算法会被评为是错误的。

2．算法效率的度量

度量算法效率的方法有两种：事后计算和事前分析估算。

（1）事后计算。先实现算法，然后运行程序，测算其对时间和空间的消耗。这种度量方法有很多弊端，由于算法的运行与计算机的软硬件等环境因素有关，不容易发现算法本身的优劣。同样的算法，用不同的编译器编译出的目标代码不一样多，完成算法所需的时间也不相同。当计算机的存储空间较小时，算法运行时间会延长。

（2）事前分析估算。这种度量方法通过比较算法的复杂性，估算算法的效率高低。算法的复杂性与计算机的软硬件环境无关，仅与计算耗时和存储需求有关。算法复杂性的度量可以分为空间复杂度度量和时间复杂度度量。

3．算法的时间复杂度

算法的时间复杂度主要用于衡量算法执行时需要消耗的时间规模。

执行算法所用的时间包括程序编译时间和运行时间，由于算法编译成功后可以多次运行，因此通常忽略掉编译时间，只讨论运行时间。

算法的运行时间取决于加、减、乘、除等基本运算的时长，参加运算的数据量，以及计算机硬件和操作环境等因素。其中，最为关键的因素是问题规模，也就是运算数据量的多少。同等条件下，问题规模越大，运行时间越长。例如，求1+2+3+…+ n 的算法，计算量的大小取决于问题规模 n 为多大， n 的规模决定了基本运算的执行次数，即运算规模。因此，算法运行时间一定是问题规模 n 的某个函数，记作 T ( n )。当 n 不断变化时， T ( n )也会不断变化。为了弄清楚 T ( n )的变化规律，引入“时间复杂度”这一概念。

一般情况下，若有某个辅助函数 f ( n )，使得当 n 趋近于无穷大时， T ( n ) / f ( n )的极限值为不等于零的常数，则称 f ( n )是 T ( n )的同数量级函数，记作 T ( n )= O ( f ( n ))。 O ( f ( n ))表示的是算法的渐进时间复杂度，这种表示法被称为大 O 表示法。需要注意，时间复杂度得出的不是时间量，而是一种增长趋势。

例如，当一个算法的时间复杂度为常量，不随数据量 n 的大小改变时，可表示为 O (1)；当一个算法的时间复杂度与 n 成线性比例关系时，可表示为 O ( n )。

4．算法的空间复杂度

算法的空间复杂度是指算法执行过程中需要的辅助空间数量。这里，辅助空间数量不是程序指令、常数、指针等占用的存储空间，也不是输入／输出数据占用的存储空间，而是除此以外算法临时开辟的存储空间。

算法的空间复杂度分析方法同时间复杂度相似。设 S ( n )表示算法的空间复杂度，则 S ( n )= O ( f ( n ))。

1.2.4　大 O 表示法

下面通过一个实例，介绍如何使用大 O 表示法判断一段程序的时间复杂度（请读者从数学函数的角度思考以下讲解内容）。

【实例1.2】 计算 a 、 b 、 c 的值。 （实例位置：资源包\Code\01\02）

已知 a + b + c =1000且 a ² + b ² = c ² （ a , b , c 都是自然数，且范围均为0～1000），求 a , b , c 的所有可能组合。代码如下：

本例程序大约需要4分钟，才能运行出结果，如图1.7所示。

将上述代码做如下修改：

比较这两段代码，发现代码的第3行有所不同，从一个for循环变成了一个减法基本运算。第二段代码的最终运行时间不到1分钟，结果依然是图1.7的内容。从速度上看，第二段代码更快。也就是说，第二段代码的算法要比第一段代码成熟，执行效率更高。这是为什么呢？一起来分析一下。

（1）首先来算下第一段代码的时间复杂度。

设时间为 f ( n )，这段代码用到了3层for循环，每层循环遍历一次0～1000，时间复杂度都是1000，3层嵌套for循环的时间复杂度是各层for循环时间复杂度的乘积，即 f ( n )=1000*1000*1000，而for循环之后的if和print两条语句是基本语句，暂且算成是2。因此，第一段程序的时间复杂度是： f ( n )=1000*1000*1000*2。

如果将for循环的遍历范围改成0～ n ， n 是一个变量，那么时间复杂度就变成了一个函数：

f ( n )= n * n * n *2=2 n ³

函数的象限图如图1.8所示。将系数从2变为1， f ( n )= n ³ 的函数图虽然没那么陡峭，但整体趋势是一样的。可以这么理解，增加系数形成的象限图都是 f ( n )= n ³ 的渐近线，对应的函数是渐近函数。

将一系列表示时间复杂度的渐近函数用 T ( n )来表示，就变成了如下形式（ k 为系数）：

T ( f ( n ))= k * f ( n )

由于系数 k 并不影响函数走势，所以可以忽略 k 的值，最终 T ( n )= O ( f ( n ))。

这种形式就是大 O 表示法， f ( n )是 T ( n )的大 O 表示法。其中， O ( f ( n ))就是这段代码的渐近函数的时间复杂度，简称时间复杂度，也就是 T ( n )。

通过上面的分析，可以总结出这样一条结论：在计算一个算法的时间复杂度时，可以忽略所有的低次幂和最高次幂的系数。这样做的目的是为了简化算法分析，使注意力集中在增长率上。

（2）下面来分析一下第二段代码的时间复杂度。

第二段代码有两层for循环，忽略系数，它的时间复杂度就是 T ( n )= n ² ，最终的大 O 表示法为 T ( n )= O ( n ² )，复杂度的走势如图1.9所示。

例如，有这样一段代码：

求这段代码的时间复杂度 T ( n )，分析如下：

（1）第一个框内的代码，只有3条基本语句，所以时间复杂度是 T ₁ ( n )=3。

（2）第二个框内的代码，有两层for嵌套循环和3条基本语句，所以时间复杂度是 T ₂ ( n )= n * n *3= n ² *3。

（3）第三个框内的代码，有一层for循环和两条基本语句，所以时间复杂度是 T ₃ ( n )= n *2。

（4）第四个框内的代码，只有一条基本语句，所以时间复杂度是 T ₄ ( n )=1。

（5）整段程序的时间复杂度是 T ( n )= T ₁ ( n )+ T ₂ ( n )+ T ₃ ( n )+ T ₄ ( n )=3+ n ² *3+ n *2+1= 3 n ² +2 n +4。忽略掉所有的低次幂、最高次幂的系数以及常数，最终的大 O 表示法是 T ( n )= O ( n ² )，其象限图正是图1.9。

下面给出算法中常见的大 O 表示法，如表1.1所示。