1.1 什么是算法 在学习算法之前，需要先理解“算法”的概念。1950年，algorithm(算法)一词经常同欧几里得算法联系在一起。这个算法就是在欧几里得的《几何原本》中所阐述的求两个数的最大公约数的过程，即辗转相除法。从此以后，algorithm这一叫法一直沿用至今。 1.1.1 一道有趣的智力题 为了理解什么是算法，先看一道有趣的智力题：假设“烧水泡茶”必须有如下5道工序：①烧开水、②洗茶壶、③洗茶杯、④拿茶叶、⑤泡茶。 在上述5个步骤中，其中①烧开水、②洗茶壶、③洗茶杯、④拿茶叶是泡茶的前提。假设①烧开水需要15分钟，②洗茶壶需要2分钟，③洗茶杯需要1分钟，④拿茶叶需要1分钟，⑤泡茶需要1分钟。 不同的人进行泡茶的步骤会有差别，例如，下面是两个人不同的“烧水泡茶”的步骤。 1．第1个人“烧水泡茶”的步骤 第一步：烧水。 第二步：水烧开后，洗刷茶具，拿茶叶。 第三步：泡茶。 2．第2个人“烧水泡茶”的步骤 第一步：烧水。 第二步：烧水过程中，洗刷茶具，拿茶叶。 第三步：水烧开后泡茶。 问题：比较这两种方法有何不同，并分析哪种方法更优。 上述两个方法都能最终实现“烧水泡茶”的功能，每种方法的3个步骤就是一种“算法”。算法是指在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说，就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法。前者是推理实现的算法，后者是操作实现的算法。 1.1.2 算法的定义 算法是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令。算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。对于同一个问题，可能会有多种不同的算法来解决，不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量，例如在前面的泡茶例子中，第2个人的操作步骤的时效性更高一点。 算法中的指令描述的是一个计算，当其运行时能从一个初始状态和(可能为空的)初始输入开始，经过一系列有限而清晰定义的状态，最终产生输出并停止于一个终态。一个状态到另一个状态的转移不一定是确定的。随机化算法在内的一些算法，包含了一些随机输入。 1.1.3 计算机中的算法 计算机虽然功能强大，能够帮助人们解决很多问题，但是计算机在解决问题时，也需要遵循一定的步骤。在编写程序实现某个项目功能时，也需要遵循一定的算法。计算机中的算法可分为如下两大类。 (1) 数值运算算法：求解数值。 (2) 非数值运算算法：事务管理领域。 假设有一个下面的运算：1×2×3×4×5，为了计算上述运算的结果，最普通的做法是按照如下步骤进行计算。 第1步：先计算1乘以2，得到结果2。 第2步：将2乘以3，计算得到结果6。 第3步：将6再乘以4，计算得24。 第4步：将24再乘以5，计算得120。 最终计算结果是120，上述第1步到第4步的计算过程就是一个算法。如果想用编程的方式来解决上述运算，通常会使用如下算法来实现。 第1步：假设定义t=1。 第2步：使i=2。 第3步：使t×i，乘积仍然放在变量t中，可表示为t×i→t。 第4步：使i的值+1，即i+1→i。 第5步：如果i≤5，返回重新执行第3步以及其后的第4步和第5步；否则，算法结束。 由此可见，上述算法方式就是数学中的“n!”公式。既然有了公式，在具体编程的时候，只需使用这个公式就可以解决上述运算的问题。 再看下面的一个数学应用问题。 假设有80个学生，要求打印输出成绩在60分以上的学生。 在此用n来表示学生学号，ni表示第i个学生学号；cheng表示学生成绩，chengi表示第i个学生成绩。根据题目要求，可以写出如下算法。 第1步：1→i。 第2步：如果chengi≥60，则打印输出ni和chengi，否则不打印输出。 第3步：i+1→i。 第4步：如果i≤80，返回步骤2，否则，结束。 由此可见，算法在计算机中的地位十分重要。所以在面对一个项目应用时，一定不要立即编写程序，而是要仔细思考解决这个问题的算法是什么。想出算法之后，以这个算法为指导思想来编程。 1.1.4 算法在编程语言中的定义 算法在计算机编程中起着举足轻重的作用，算法已经成为衡量一名程序员水平高低的参照物。水平高的程序员都会看重数据结构和算法的作用，这样能开发出更高效的程序代码。开发者的水平越高，就越能理解算法的重要性。算法不仅仅是运算工具，它更是程序的灵魂。在现实项目开发过程中，很多实际问题需要精心设计的算法才能有效解决。 算法是计算机处理信息的基础，因为计算机程序本质上是一个算法，告诉计算机确切的步骤来执行一个指定的任务，如计算职工的薪水或打印学生的成绩单。通常，当算法在处理信息时，数据会从输入设备读取，写入输出设备，也能保存起来供以后使用。 著名计算机科学家沃思提出了下面的公式。 数据结构+算法=程序 实际上，一个程序应当采用结构化程序设计方法进行程序设计，并且用某一种计算机语言来表示。因此，可以用下面的公式表示。 程序=算法+数据结构+程序设计方法+语言和环境 上述公式中的4个方面是一种程序设计语言所应具备的知识。在这4个方面中，算法是灵魂，数据结构是加工对象，语言是工具，编程需要采用合适的方法。其中，算法是用来解决“做什么”和“怎么做”的问题。实际上程序中的操作语句就是算法的体现，所以说，不了解算法就谈不上程序设计。数据是操作对象，对操作的描述即是操作步骤，操作的目的是对数据进行加工处理以得到期望的结果。举个通俗点的例子，厨师做菜肴，需要有菜谱。菜谱上一般应包括：①配料(数据)、②操作步骤(算法)。这样，面对同一原料可以加工出不同风味的菜肴。 1.2 衡量算法的优劣 在现实应用中有多种常用的算法思想，如何比较算法思想的效率孰优 孰劣呢？本节简要介绍衡量算法是否优劣的知识。 1.2.1 衡量算法优劣的标准 1. 衡量算法优劣的5个标准 衡量算法是否优劣有以下5个标准。 (1) 确定性。算法的每一种运算必须有确定的意义，该种运算应执行何种动作应无二义性，目的明确。 (2) 可行性。要求算法中待实现的运算都是可行的，即至少在原理上能由人用纸和笔在有限的时间内完成。 (3) 输入。一个算法有零个或多个输入，在算法运算开始之前给出算法所需数据的初值，这些输入来自特定的对象集合。 (4) 输出。输出是算法运算的结果，一个算法会产生一个或多个输出，输出同输入具有某种特定关系。 (5) 有穷性。一个算法总是在执行了有穷步的运算后终止，即该算法是有终点的。 2. 衡量算法效率的方法 通常有以下两种衡量算法效率的方法。 (1) 事后统计法。该方法的缺点是必须在计算机上实际运行程序，容易被其他因素掩盖算法本质。 (2) 事前分析估算法。该方法的优点是可以预先比较各种算法，以便均衡利弊而从中选优。 3. 与算法执行时间相关的因素以及时间复杂度 与算法执行时间相关的因素如下：①算法所用“策略”；②算法所解问题的“规模”；③编程所用“语言”；④“编译”的质量；⑤执行算法的计算机的“速度”。 在上述因素中，后3条受计算机硬件和软件的制约，因为是“估算”，所以只需考虑前两条即可。 事后统计容易陷入盲目境地，例如，当程序执行很长时间仍未结束时，不易判别是程序错了还是确实需要那么长的时间。 一个算法的“运行工作量”通常是随问题规模的增长而增长，所以应该用“增长趋势”来作为比较不同算法的优劣的准则。假如，随着问题规模n的增长，算法执行时间的增长率与f(n)的增长率相同，则可记作：T(n) = O(f(n))，称T(n)为算法的(渐近)时间复杂度。 究竟如何估算算法的时间复杂度呢？任何一个算法都是由一个“控制结构”和若干“原操作”组成的，所以可以将一个算法的执行时间看作所有原操作的执行时间之和，即 (原操作(i)的执行次数×原操作(i)的执行时间)。 算法的执行时间与所有原操作的执行次数之和成正比。对于所研究的问题来说，从算法中选取一种基本操作的原操作，以该基本操作在算法中重复执行的次数作为算法时间复杂度的依据。以这种衡量效率的办法所得出的不是时间量，而是一种增长趋势的量度。它与软硬件环境无关，只暴露算法本身执行效率的优劣。 1.2.2 算法复杂度 算法复杂度是指算法在编写成可执行程序后，运行时所需要的资源，这些资源包括时间资源和内存资源。同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。 1. 时间频度 一个算法执行所耗费的时间，从理论上来说必须上机运行测试才能知道。但是我们不可能也没有必要对每个算法都进行上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比，哪个算法中语句执行次数多，它花费的时间就越多。一个算法中的语句执行次数称为语句频度或时间频度，记为T(n)。 2. 时间复杂度 算法的时间复杂度是指执行算法所需要的计算工作量。在刚才提到的时间频度中，n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此，我们引入时间复杂度的概念。在一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，存在一个正常数c使得f(n)*c≥T(n)恒成立，记作T(n)=O(f(n))，称O(f(n))为算法的渐近时间复杂度，简称时间复杂度。 在各种不同算法中，若算法中语句执行次数为一个常数，则时间复杂度为O(1)。另外，在时间频度不相同时，时间复杂度有可能相同，如T(n)=n2+3n+4与T(n)=4n2+2n+1，它们的频度不同，但时间复杂度相同，都为O(n2)。 在计算时间复杂度时需要遵循如下原则：  用常数1来取代运行时间中所有加法常数；  只要高阶项，不要低阶项；  不要高阶项系数。 在现实中常见的时间复杂度如下。  O(1)：常数阶；  O(n)：线性阶；  O(log2n)：对数阶；  O(nlogn)：线性对数阶；  O(n2)：平方阶。 算法的时间复杂度是一个函数，它定量描述了该算法的运行时间，通常用“O”来表示时间复杂度。在使用这种方式时，时间复杂度可被称为渐近的，它考察当输入值大小趋近无穷时的情况。时间复杂度是用来估计算法运行时间的一个式子(单位)，一般来说，时间复杂度高的算法比复杂度低的算法慢。例如在下面的实例文件time01.py中，演示了不同类型Python程序的时间复杂度。 print('Hello world') # O(1) # O(1) print('Hello World') print('Hello Python') print('Hello Algorithm') for i in range(n): # O(n) print('Hello world') for i in range(n): # O(n^2) for j in range(n): print('Hello world') for i in range(n): # O(n^2) print('Hello World') for j in range(n): print('Hello World') for i in range(n): # O(n^2) for j in range(i): print('Hello World') for i in range(n): for j in range(n): for k in range(n): print('Hello World') # O(n^3) 在Python程序中，几次循环就是n的几次方的时间复杂度。例如在下面的代码中， 26 = 64，log264 = 6，所以循环减半的时间复杂度为O(log2n)，即O(logn)。如果是循环减半的过程，则时间复杂度为O(logn)或O(log2n)。 n = 64 while n > 1: print(n) n = n // 2 常见的时间复杂度高低排序是： O(1)