本节书摘来自华章出版社《数据结构与算法：Python语言描述》一书中的第1章，第1.3节，作者 裘宗燕，更多章节内容可以访问云栖社区“华章计算机”公众号查看

1.3算法和算法分析

本节集中讨论算法的问题，特别是算法的性质及其分析技术。

1.3.1问题、问题实例和算法

在考虑计算问题时，需要清晰地区分问题、问题实例和算法三个概念，并理解它们之间的关系，这就是本小节讨论的内容。
三个基本概念
考虑一个计算问题时，需要注意到三个重要概念：
问题：一个问题W是需要解决（需要用计算求解）的一个具体需求。例如判断任一个正整数N是否为素数，求任一个方形矩阵的行列式的值等。虽然可以严格定义“问题”的概念，但在这里还是想依靠读者的直观认识。总而言之，现实世界中存在许许多多需要用计算解决的问题，它们是研究和实现算法的出发点。
问题实例：问题W的一个实例w是该问题的一个具体例子，通常可以通过一组具体的参数设定。例如判断1013是否为素数，或者求一个具体方形矩阵的行列式的值。显然，一个问题反映了其所有实例的共性。
算法：解决问题W的一个算法A，是对一种计算过程的严格描述。对W的任何一个实例w，实施算法A描述的计算过程，就能得到w的解。例如，一个判断素数的算法应该能给出1013是否为素数的判断，也能判断其他正整数是否为素数；一个求矩阵的行列式值的算法必须能应用于任何矩阵，得到其行列式的值。
下面是一些计算问题及其实例：
求两个（两维）矩阵的乘积，求任意两个具体矩阵的乘积都是其实例。
将一个整系数多项式分解为一组不可约整系数多项式因子的乘积，计算具体多项式的因式是这个问题的实例。
将一个图像旋转90度，其实例是要求旋转的各种具体图像。
辨认出数字相机取景框里的人脸，每次拍照的取景框图像都是其实例。
要用计算机解决问题，需要开发能解决该问题的方法（和算法），然后实现相关的程序。解决一个问题的算法应能统一求解该问题的（所有）实例。对于一个可以用计算机解决的问题，完全可能有多种不同的算法。
算法的性质
一个算法是对一种计算过程的一个严格描述，人们通常认为算法具有如下性质：
有穷性（算法描述的有穷性）：一个算法的描述应该由有限多条指令或语句构成。也就是说，算法必须能用有限长的描述说清楚。
能行性：算法中指令（语句）的含义严格而且简单明确，所描述的操作（计算）过程可以完全机械地进行。
确定性：作用于所求解问题的给定输入（以某种描述形式给出的要处理问题的具体实例），根据算法的描述将产生出唯一的确定的一个动作序列。使用算法就是把问题实例（的表示）送给它，通过确定性的操作序列，最终得到相应的解。
终止性（行为的有穷性）：对问题的任何实例，算法产生的动作序列都是有穷的，它或者终止并给出该问题实例的解；或者终止并指出给定的输入无解。
输入/输出：有明确定义的输入和输出。
满足确定性的算法也称为确定性算法。实际上，现在人们也关注更广泛的概念，例如考虑各种非确定性的算法，如并行算法、概率算法等。另外，人们也关注并不要求终止的计算描述，这种描述有时被称为过程（procedure）。
解决重要问题的算法不仅具有理论价值，也有实际价值。例如：
Google、百度等网络搜索公司开发和使用的各种网络检索和排名算法，它们能有效地利用大量计算机设备，收集和整理存在于互联网上的大量杂乱无章的信息，满足网络用户的需要。其中非常关键的一件事是对与用户请求有关的信息做出很好的排序，把最可能满足用户需要的信息排在最前面，称为ranking（排名）。
现代社会特别重视信息的传播和存储的安全性，在社会生活中使用越来越广泛的电子金融、电子商务，都对安全性提出了特别的要求。而计算机网络和网络服务的安全性依赖于所用的加密方法，高安全和高效率的加密解密算法极端重要。
算法的描述
前面说一个算法严格地描述了一种计算过程，但并没有说算法描述的形式和方式。实际上，算法与数学中的定义和定理类似，通常用于人与人之间的交流，但交流的内容是问题的解决过程，有关一个计算应该如何进行。主要目的是帮助人理解和思考相应的问题求解方法、技术和过程。由于主要为了人们阅读和使用，算法可以采用不同的描述形式，需要在易读、易理解和严格性之间取得某种平衡。算法的描述应基于清晰定义的概念，包含足够多的细节，使人可以按照算法一步步工作完成具体问题实例的求解。常见的描述形式如：
采用自然语言描述。用自然语言描述的计算过程可能比较容易阅读，但可能比较冗长啰唆，也容易出现歧义，造成读者的误解。
采用在自然语言描述中结合一些数学记法或公式的描述形式。这是前一描述形式的变形，主要是为了简洁、严格（消除歧义），减少误解的可能性。
采用严格定义的形式化记法形式描述。例如：
采用某种通用的计算模型描述方式，如采用著名的图灵机模型，用一个完成相应计算的图灵机描述算法。这种描述完全是严格的，没有歧义，但通常会非常繁琐，极难阅读，而且难以进一步使用。
采用某种严格的专门为描述算法而定义的形式化描述语言。这样做可以避免歧义性，但目前还没有公认最为适用的语言。
用类似某种编程语言的形式描述算法过程，其中掺杂使用一些数学符号和记法，用于描述算法中一些细节和具体操作。前面实例中采用了类似Python的控制结构，结合自然语言和数学符号。利用编程语言的控制结构，可以简洁、清晰地反映算法中操作的控制、执行条件和执行顺序，常可以得到较为简洁的算法描述。这种方式的问题是可能涉及过多细节，不利于跨语言使用。这类问题应尽量避免。
采用某种伪代码形式，结合编程语言的常用结构、形式化的数学记法代表的严格描述和自然语言。这种方式与前一方式类似，但不过多拘泥于具体语言。
目前最常见的是后两种描述形式。在本书中需要描述算法时，通常采用Python语言程序的形式，结合自然语言和数学表达形式，主要用于局部的功能说明。
算法和程序
计算问题通常都很复杂，问题实例可能很大，解决它们需要执行数以千万计的具体操作。人工计算只能处理极简单问题的规模很小的实例，不能完成大规模计算。要解决有一定规模、有实际价值的问题，必须借助于能自动运行的计算机器。今天能利用的就是常见的电子计算机。要指挥其工作，就需要做出计算机能执行的程序。
程序可以看作采用计算装置能够处理的语言描述的算法，由于它是算法的实际体现，又能在实际计算机上执行，因此被称为算法的实现。
程序可能用各种计算机语言描述。例如用直接对应于特定计算机硬件的机器语言或者汇编语言。也可以用通用的高级编程语言，如C、Java等。本书中将用Python语言描述程序，定义各种数据结构，描述各种算法。
程序和算法密切相关。在每一个程序背后都隐藏着一个或者一些算法。如果一个程序正确实现了一个能解决某个问题的算法，用这个程序处理该问题的实例就应该得到相应的解。此外，该程序运行时的各种动态性质，也应该反映它所实现的算法的性质，这样才是相应算法的合理实现。下面还会进一步讨论这个问题。
另一方面，由于程序是用计算机能处理的某种具体编程语言描述的，其中必然会包含一些与具体语言有关的细节结构和描述方式方面的特征。所用的语言不同，不仅可能影响算法描述的方便性，也可能影响到程序的运行效率。
由于这些情况，在抽象地考虑一个计算过程或考虑一个计算过程的抽象性质时，人们常用“算法”作为术语，用于指称相应计算过程的描述。而在考虑一个计算在某种语言里的具体实现和实现中的问题时，人们常用“程序”这一术语讨论相关问题。本书也采用这种通行的做法。此外，有时书中描述的是一个程序，但在讨论时却说“算法”。这时实际想说的就是该程序背后的与具体语言无关的计算过程。
算法设计与分析
算法是计算机科学技术中最重要的研究课题，其具体应用遍及计算机科学技术的所有研究和应用领域。由于算法的重要性，人们也对算法设计和开发的经验做了许多总结，这一研究领域称为算法设计与分析。
一方面，所谓算法设计，就是从问题出发，通过分析和思考最终得到一个能解决问题的过程性描述的工作过程。算法设计显然是一种创造性工作，需要靠人的智慧和经验，不可能自动化。实际应用问题千变万化，解决它们的算法的表现形式也多种多样。但是许多算法的设计思想有相似之处，相关工作也有规律性可循。人们深入研究了前人在算法领域的工作经验和成果，总结出了一批算法设计的重要思路和模式。对算法设计方法做分类研究，可以给后人的学习提供一些指导。已有的设计经验和模式可能提供一些有用的线索和启发，供人们在设计解决新问题的新算法时参考。
算法设计中一些常见的通用想法可以称为算法设计模式。常见模式包括：
枚举法。根据具体问题枚举出各种可能，从中选出有用信息或者问题的解。这种方法利用计算机的速度优势，在解决简单问题时十分有效。
贪心法。如前所述，根据问题的信息尽可能做出部分的解，并基于部分解逐步扩充得到完整的解。在解决复杂问题时，这种做法未必能得到最好的解。
分治法。把复杂问题分解为相对简单的子问题，分别求解，最后通过组合起子问题的解的方式得到原问题的解。
回溯法（搜索法）。专指通过探索的方式求解。如果问题很复杂，没有清晰的求解路径，可能就需要分步骤进行，而每一步骤又可能有多种选择。在这种情况下，只能采用试探的方式，根据实际情况选择一个可能方向。当后面的求解步骤无法继续时，就需要退回到前面的步骤，另行选择求解路径，这种动作称为回溯。
动态规划法。在一些复杂情况下，问题求解很难直截了当地进行，因此需要在前面的步骤中积累信息，在后续步骤中根据已知信息，动态选择已知的最好求解路径（同时可能进一步积累信息）。这种算法模式被称为动态规划。
分支限界法。可以看作搜索方法的一种改良形式。如果在搜索过程中可以得到一些信息，确定某些可能的选择实际上并不真正有用，就可以及早将其删除，以缩小可能的求解空间，加速问题求解过程。
这里需要说明两点：首先，上述算法设计模式只是人们对经验的总结，只能借鉴，不应作为教条。其次，这些模式并不相互隔绝也不互相排斥。例如，一般而言复杂的问题都需要分解；而最简单的情况经常可能采用枚举和判断的方式处理。所以，在很多复杂算法中可以看到多种算法模式的身影，是多种模式的有机组合。还是应该强调，对于算法设计而言，并没有放之四海而皆准的设计理论或技术，只能借鉴和灵活运用前人经验。算法是智力活动的产物，一个好算法至少等价于一个好的定理及其证明，因为算法不仅说明了一件事可以用计算机处理，而且还可以实现为程序，真正利用计算机去解决问题。
在设计和使用算法的过程中，人们也深入地研究了算法的各种性质，包括所有算法共有的性质和一些具体算法的具体性质。在算法的共有性质中，最重要的就是算法的实施都需要耗费资源，即一个算法的实施必定蕴涵着一定量的时间和空间开销。算法分析的主要任务就是弄清算法的资源消耗。下一小节将专门讨论这个问题。算法分析的最重要作用是作为评价算法的一种标准。例如，解决同一个问题常常可以设计出多个不同算法，显然，工作中消耗时间和空间更少的算法通常更为可取。

1.3.2算法的代价及其度量

在研究现实世界中的计算问题时，必须考虑计算的代价。原因也很清楚：一方面，实际的计算机是一种物理设备，执行每个操作都耗费时间。虽然今天的计算机非常快，每秒可以完成数以十亿计的操作，但每次操作还是需要一点点时间，而大量的一点点时间累积起来就可能超过任意大的固定的时间限制。另一方面，计算中都需要保存被处理的数据，为了完成复杂计算，通常还需要保存许多中间结果。虽然今天最普通的计算机也有数以十亿计的存储单元，但其存储量毕竟不是无穷大，总有可能用完。
在考虑求解一个问题的具体算法时，需要考虑用它解决问题的代价，包括该算法：在求解过程中需要多少存储空间？完成问题实例的求解需要多长时间？使用者需要关心算法运行中存储占用的高位限，以及得到结果的时间。
度量的单位和方法
实际计算机的种类很多，其中各种操作的执行速度、存储单元具体大小都可能不同。对于算法的理论研究应该具有一定的抽象性，应该排除具体机器的非普遍性特征，抽象地反映算法的共性和本质，这样得到的抽象研究结果才有更广泛的指导意义。为了抽象地研究算法的性质，需要做一些简单假设：
所用的计算设备中为数据存储准备了一组基本单元，每个单元只能保存固定的一点有限数据。在考虑算法的时间性质时，将以此作为空间的单位。
机器能执行一些基本操作，计算中的一次操作消耗一个单位的时间。
在考虑具体的算法时，可以根据需要选择合理的存储单位，只要求其大小固定且有穷，以其计数值作为存储开销（空间开销）的基本度量。另一方面，可以根据情况选择一组合适的操作，假定执行它们需要一个单位时间，以其执行次数作为时间开销的基本度量。
作为评价算法的尺度，需要有一种合理的度量方法。现在首先讨论这个问题，讨论中主要考虑计算的时间开销，空间开销的情况类似，不再另行说明。
假设有了解决某具体计算问题W的一个具体算法A，现在需要考虑A在计算中的时间开销。根据前面的讨论，算法A应该能处理问题W的任何实例。然而，同属一个问题的实例也有大有小，实例的规模不同，算法求解中需要付出的代价也可能不同。例如，采用同一个算法，判断1013是否为素数或判断10013131301131是否为素数，需要花费的时间通常是不同的。计算矩阵行列式值的问题更加明显，要计算3×3矩阵的行列式，只牵涉到9个元素的处理，而计算3000×3000矩阵的行列式，牵涉到的元素多了一百万倍，需要做更多运算，所需要的时间必然会多得多。
现在需要度量的是算法，同一个算法能应用于不同的实例，计算的实际代价通常与实例的规模（大小）有关。人们自然希望对一个算法的度量结果能适用于任何实例，因此这种度量必须反映实例的规模对计算开销的影响。为了处理这种情况，人们提出的方法是把一个算法的计算（时间和空间）开销定义为问题的实例规模的函数。也就是说，算法分析就是针对一个具体算法，设法确定一种函数关系，以问题实例的某种规模n为参量，反映出这个算法在处理规模n的问题实例时需要付出的时间（或者空间）代价。
把算法的代价看作规模的函数之后，很容易看到一种必然出现的情况：可能有一些算法，随着实例规模的增长，其时间（或空间）开销的增长非常快，而另一些算法的开销函数随着规模增长而增长得比较慢。这种相异的函数关系实际上反映了算法的性质。从高等数学的角度看，这种函数关系描述一种增长趋势：在规模n趋向于无穷的过程中，有关函数的增长速度。下面将这两个函数关系称为算法的时间代价和空间代价。
与实例和规模有关的两个问题
这里还有两个问题需要说明。首先是问题实例的规模，这是分析一个算法时采用的基本尺度，算法的代价将基于它描述。尺度不同，有关算法代价的结论就会不同。实际情况会怎么样呢？先看看具体实例中的情况。
对判断素数的问题，有两个尺度可能作为实例的规模度量。一种可能是用被检查整数的数值，另一种可能是取被检查整数按某种进制（例如十进制或二进制）表示的数字串长度。这里出现了一个大问题：整数的数值与其进制表示的数字串长度之间有着指数关系，长m的数字串可以表示数值直至Bm－1的整数，其中B为进制的基数（例如10或者2）。对矩阵行列式问题也有两种可能，可以取矩阵的维数作为尺度，或者取矩阵中的元素个数。两者之间也有一个平方的差异。虽然上述几种尺度选择好像都有道理，但是，选择不同的尺度描述算法的代价，就会得到很不一样的结果。
对算法的一般性研究不仅希望比较解决同一个问题的不同算法，还希望对解决不同问题的算法之间的关系有所认识。因此，人们希望有一种统一的尺度作为基础来讨论算法的代价。由于问题实例对应于算法的输入，送给素数判断算法的输入就是可能长也可能短的数字串，送给矩阵行列式算法的是表示矩阵的那一组元素。对实例的规模，最直接的反映就是输入数据的多少，这种看法覆盖了一切计算问题和算法。
按照上述观点，对于判断素数的问题，应该用整数表示的数字串长度作为问题规模的尺度；而对于矩阵的行列式求值，应该用矩阵元素的个数（或者元素个数乘以每个元素的表示长度，这里差一个常量因子）。对一些具体问题，有时人们也有习惯的做法。例如对于与矩阵有关的算法，人们讨论时经常用矩阵维数作为规模的尺度。按照这种做法给出的算法代价，与基于矩阵元素个数描述就差了一个平方。
还有一个问题也值得注意：使用同一个算法解决问题时，即使对于同样规模的实例，计算的代价也可能不同。以素数判断算法为例，同样由100个十进制数字表示的数，如果被判断的是偶数，算法启动后只需做一次检查，立刻就可以给出否定的结果；如果是奇数，就需要花更多时间。在这方面，处理不同问题的算法，其性质也可能不同。
考虑处理数值表（数值序列）的两个问题：如果希望求出表中数据的平均值，任何算法都需要先求出所有数据之和，对同样大小的实例，计算的代价都差不多。如果问题是找到数据中第一个小于0的项，情况就很不一样。采用顺序检查的算法处理同样包含10000个数据的表，有时很快就能得到结果，有时则要检查完所有的数据。
针对这种情况，在度量算法A的代价时（以时间为例），存在几种可能的考虑。在处理规模为n的问题实例时，考虑：
算法A完成工作最少需要多少时间？
算法A完成工作最多需要多少时间？
算法A完成工作平均需要多少时间？
第一种考虑的价值不大，因为它没提供什么有用信息。在实际中也是如此，对完成工作所需时间的最乐观的估计基本上没有价值。
第二种考虑提供了一种保证，说明在这段时间之内，本算法一定能完成工作。这种代价称为最坏情况的时间代价。
第三种考虑是希望对算法A做一个全面评价（处理规模为n的实例的平均时间代价），因此它完整全面地反映了这个算法的性质。但另一方面，这个时间代价并没有保证，不是每个计算都能在这一时间内完成。此外，“平均”还依赖于所选的实例，以及这些实例出现的概率。通常总需要做一些假定，例如假定规模同为n的各种实例是均匀分布的。然而在应用实践中，实际问题实例有自己的分布情况，未必与理论分布一致，而实际中的真实分布通常很难确定。这些都给平均代价概念的应用带来困难。
在有关算法的研究和分析中，人们主要关注算法的最坏情况代价，有时也关注算法的平均代价。本书后面的章节里也这样考虑。
常量因子和算法复杂度
对一个具体程序进行细致分析，有可能弄清在用它处理一个具体实例的过程中，各种操作执行的具体次数。通过对一些不同规模实例的分析，也有可能把得到的操作次数总结为问题实例规模的一个具体函数。当然，这样做牵涉到很多细节，再加上程序描述中可能出现分支的情况，给出一个统一的精确描述经常是非常困难的。
对于抽象的算法，通常无法做出精确度量。在这种情况下只能退而求其次，设法估计算法复杂性的量级。另一方面，分析算法性质是为了算法的设计和评价，最终是为了用程序实现算法。由于程序运行所用的计算机、描述程序的语言、实现方法等不同，同样算法在实际运行中所需的时间也可能有些变化。
这些情况说明，特别具体的细致分析虽然很好，但在实践中的价值有限。对于算法的时间和空间性质，最重要的是其量级和趋势，这些是代价的主要部分，而代价函数的常量因子可以忽略不计。例如，可以认为3n2和100n2属于同一个量级，如果两个算法处理同样规模实例的代价分别为这两个函数，就认为它们的代价“差不多”。基于这些考虑，人们提出描述算法性质的“大O记法”。
首先给出“大O记法”的严格定义：对于单调的整数函数f，如果存在一个整数函数g和实常数c＞0，使得对于充分大的n总有f(n)≤c•g(n)，就说函数g是f的一个渐近函数（忽略常量因子），记为f(n)＝O(g(n))。易见，f(n)＝O(g(n))说明在趋向无穷的极限意义下，函数f的增长速度受到函数g的约束。
把上述描述方式应用于算法的代价问题。假设存在函数g，使得算法A处理规模为n的问题实例所用的时间T(n)＝O(g(n))，则称O(g(n))为算法A的渐近时间复杂度，简称时间复杂度。算法的空间复杂度S(n)的定义与此类似。
这里有几点说明。
首先，如果T(n)＝O(g(n))，那么对于任何增长速度比g(n)更快的函数g′(n)，显然也有T(n)＝O(g′(n))。这说明上述定义考虑的是算法复杂度的上限。虽然这种描述并不精确，但对于本书的讨论以及很多计算机实践已经足够了。
其次，虽然可以选择任意的合适的函数作为描述复杂性时使用的g(n)，但是一组简单的单调函数已足以反映人们对基本算法复杂度的关注。在算法和数据结构领域，人们最常用的是下面这组渐近复杂度函数：
O(1)，O( log n)，O(n)，O(n log n)，O(n2 )，O(n3)，O(2n)
在后面讨论中，也经常把O(1)称为常量复杂度，把O(log n)称为对数复杂度，把O(n)称为线性复杂度，把O(n2)称为平方复杂度，把O(2n)称为指数复杂度，等等。注意，根据前面脚注，在考虑量级时对数的底并不是主要因素（可能差一个常量因子），因此可以忽略。另外，一个算法的时间复杂度为O(n)，也常说这个算法是O(n)时间的算法，或者说这个算法需要O(n)时间等。

按照上面的理论，如果算法的改进只是加快了常量倍，也就是说减小了复杂性函数中的常量因子，算法的复杂度没有变化。但是，在许多实际情况中，这种改进也可能是很有意义的。例如，需要3天时间算出明天的天气预报，与只需要半天时间就能算出明天的天气预报，算法的实际价值是截然不同的。前者毫无价值而后者就能实用了。理论分析主要是给出了一种基本趋势，使人可以从较为宏观的角度认识所用的算法。
如果有T(n)＝O(g(n))（或者S(n)＝O(g(n))），函数g(n)是算法的实际时间开销的一个上界，并不表示实际开销真正具有与g(n)同样的增长速度（只说明其增长速度不超过g(n)）。进一步说，也可以考虑复杂性的下界（算法代价的增长速度不低于……），或者上确界。一些算法分析书籍里引进了不同的记法表示这些概念。本书中将只所用“大O记法”，但在分析算法时，尽可能考虑“紧的”上界。对一些复杂的算法，找出其时间或空间开销的上确界很不容易。总而言之，“大O记法”给出的也是一种保证。
算法复杂度的意义
不难看出，算法的复杂度分级相当于（高等数学里）无穷大的阶，反映了在规模n趋于无穷大的过程中，算法代价增长的速度。算法的复杂度越高，其实施的代价随着规模增大而增长的速度就越快。问题是，这种情况很重要吗？
看一个例子。假设解决某个具体问题的基本操作每秒钟可以完成106次，需要处理的问题实例的规模是100。如果算法的时间复杂度是O(n)，计算所需的时间可忽略不计（1/10000秒的量级）；如果算法的时间复杂度是O(n3)，所需时间是1秒钟的量级；而如果算法的时间复杂度是O(2n)，求解问题所需时间将达到1016年的量级（注意，迄今为止的宇宙寿命估计为1010年的量级，可见上面的时间有多长）。如果计算机的速度提高10000倍，这个时间可以缩短到1012年的量级，仍然是无法接受的。
可见，算法的复杂度反过来决定了算法的可用性。如果复杂度较低，算法就可能用于解决很大的实例，而复杂度很高的算法只能用于很小的实例，可用性很有限。算法的复杂度有重要的实际意义，决定了一些算法是否真正能用于实际（具体使用的机器是否提供了足够多的存储，算法在实际要求的时间内能否完成）。例如：
做天气预报的程序，必须今天下午完成对明天的天气预报计算。如果不能按时计算出预报结果，这个算法就毫无价值。
数字相机的人脸识别程序，必须在几分之一秒内完成工作。过慢的算法会带来糟糕的用户体验，照相机的制造商不可能采用。对于这类问题，没有绝对的正误标准，如果找不到效率够高的好算法，可以考虑不那么准确但更快速的算法。
解决同一问题的不同算法
解决同一个问题可能存在不同算法。考虑一个简单问题：求斐波那契数列的第n项。根据斐波那契数列的数学定义，其第n项Fn定义如下：

根据这个定义可以直截了当地写出一个递归算法（用Python函数表示）：

def fib(n):
    if n < 2:
        return 1
    else:
        return fib(n-1) + fib(n-2)

把参数n看作问题实例的规模，不难看出，计算Fn的时间代价（考虑求加法操作的次数）大致等于计算Fn―1和Fn―2的时间代价之和。这一情况说明，计算Fn的时间代价大致等比于斐波那契数Fn的值。根据已有的结论：

括号里的表达式约等于1.618，所以计算Fn的时间代价按n值的指数增长。对于较大的n，这一计算就需要很长很长时间。
求斐波那契数还有另一个简单的递推算法：对F0和F1（如果n等于0或1）直接给出结果1；否则从Fk-1和Fk-2递推计算Fk，直至k等于n时就得到了Fn。
对应Python函数实现也很简单：

def fib(n):
    f1 = f2 = 1
    for k in range(1, n):
        f1, f2 = f2, f2 + f1
    return f2

用这个算法计算Fn的值，循环前的工作只做一次，循环需要做n－1次。每次循环中只执行了几个简单动作，总的工作量（基本操作执行次数）与n值呈某种线性关系。
这个例子说明，解决同一问题的不同算法，其计算复杂度的差异可以很大，甚至具有截然不同的性质。通过分析算法（程序）复杂度，可以帮助使用者选择适用的算法；也可能发现已知算法的复杂性都太高，促使人们设法开发更好的算法。
当然，实际中遇到的情况未必像上面求斐波那契数列的两个算法这样黑白分明。在实际工作中也经常遇到一些情况，其中两个（或多个）可用算法各有所长，例如一个时间复杂度较低但空间复杂度较高，另一个的情况正好相反。在这种情况下，就需要做进一步的细致分析，权衡利弊，选择最适合实际情况的算法。

1.3.3算法分析

算法分析的目的是推导出算法的复杂度，其中最主要技术是构造和求解递归方程，后面将简单介绍这方面的一些情况。由于本书中讨论的算法结构都比较简单，一般不需要高级的分析和推导技术。
基本循环程序
这里只考虑算法的时间复杂度，考虑最基本的循环程序，其中只有顺序组合、条件分支和循环结构。分析这种算法只需要几条基本计算规则：
0.基本操作，认为其时间复杂度为O(1)。如果是函数调用，应该将其时间复杂度代入，参与整体时间复杂度的计算。
1.加法规则（顺序复合）。如果算法（或所考虑算法片段）是两个部分（或多个部分）的顺序复合，其复杂性是这两部分（或多部分）的复杂性之和。以两个部分为例：
T(n)＝T1(n) ＋T2(n)＝O(T1(n))＋O(T2 (n))＝O(max(T1(n), T2(n)))
其中T1(n)和T2(n)分别为顺序复合的两个部分的时间复杂度。由于忽略了常量因子，加法等价于求最大值，取T1 (n)和T2 (n)中复杂度较高的一个。
2.乘法规则（循环结构）。如果算法（或所考虑的算法片段）是一个循环，循环体将执行T1 (n)次，每次执行需要T2 (n)时间，那么：
T (n)＝T1 (n)×T2 (n)＝O (T1 (n))×O (T2 (n))＝O (T1 (n)×T2 (n))
3.取最大规则（分支结构）。如果算法（或所考虑算法片段）是条件分支，两个分支的时间复杂性分别为T1 (n)和T2 (n)，则有：
T (n)＝O (max (T1 (n), T2 (n)))
现在看一个简单实例。矩阵乘法由下面程序片段完成，它求出两个n×n矩阵m1和m2的乘积，存入另一个n×n矩阵m。假设矩阵在Python语言里实现为两层的表，两个参数矩阵已经有值，保存结果的m也已准备好，计算过程可描述为：

for i in range(n):
    for j in range(n):
        x = 0.0
        for k in range(n):
            x = x + m1[i][k] * m2[k][j]
        m[i][j] = x

这个程序片段是一个两重循环，循环体是一个顺序语句，其中还有一个内嵌的循环。根据上面的复杂性计算规则，可以做出下面推导：
T(n)＝O(n)×O(n)×(O(1)＋O(n)×O(1)＋O(1))

＝O(n)×O(n)×O(n)＝O(n×n×n)＝O(n3)

其中O(1)＋O(n)×O(1)＋O(1)部分表示循环体的复杂度，它包含两个基本语句和一个简单循环，化简后也得O(n)。
再看另一个实例：求n阶方形矩阵的行列式的值。考虑两种不同算法。
高斯消元法：通过逐行消元，把原矩阵变换为一个上三角线矩阵，最后乘起所有对角线元素，就得到矩阵行列式的值。
算法如下：

设被求值矩阵为二维表A0:n

for i in range(n-1):
　　用Ai将Ai+1:n的值都变为0
det = 0.0
for i in range(n):
　　det += Ai
最后求乘积的循环需要O(n)时间。前一步的消元循环从i等于0做到i等于n-2，对i迭代时需要做n-i-1行的消元，在每行对n-i个矩阵元素做乘法和减法运算，总的时间开销不超过O(n2)，因此算法的时间复杂度是O(n3)。
考虑另一个算法：直接基于矩阵行列式的定义。这个算法是递归的，为计算n阶方阵的行列式时需要算出n个n－1阶的行列式，每计算一个n－1阶行列式需要算出n－1个n－2阶的行列式……因此有下面推导：
T(n)＝n×((n－1)2＋T(n－1))＞n×T(n－1)
＞n×(n－1)×T(n－2)＞O(n!)
其中的平方项表示构造低阶矩阵的开销。复杂度O(n!)比O(n2)增长得快得多，因此这个算法的复杂度极高，只能处理很小的矩阵，基本不实用。
递归算法的复杂度*
这里简单介绍有关递归算法复杂度的理论结果，供读者参考。实际上，循环算法也可以看成简单的递归算法，但因为较简单，不用这里的结果大都可以处理。
递归算法通常具有如下的算法模式：

def recur(n):
    if n == 0:
        return g(...)
    somework
    for i in range(a):
        x = recur(n/b)
        somework
    somework

也就是说，n值为0时直接得到结果，否则原问题将归结为a个规模为n/b的子问题，其中a和b是由具体问题决定的两个常量。另外，在本层递归中还需要做一些工作，上面描述里用somework表示，其时间复杂度可能与n有关，设为O(nk)。这个k也应该是常量，k＝0表示这部分工作与n无关。这样就得到了下面的递归方程：

有如下结论：
如果a＞bk，那么T(n)＝O(nlogba)。
如果a＝bk，那么T(n)＝O(nklog n)。
如果a＜bk，那么T(n)＝O(nk)。
这些结论可以涵盖很大一部分递归定义算法（程序）的情况。
注意，因为这里要求a、b、k为常量，由此有关结论不能处理前面行列式的递归计算，在那里规模为n的问题归结为n个规模为n－1的问题。

1.3.4Python程序的计算代价（复杂度）

本书将一直用Python语言编写程序。由于Python程序是算法的实现，因此也可以而且经常需要考虑其复杂度问题。
时间开销
在考虑Python程序的时间开销时，有一个问题特别需要注意：Python程序中的很多基本操作不是常量时间的。
下面是一些情况：
基本算术运算是常量时间操作，逻辑运算是常量时间运算。
组合对象的操作有些是常量时间的，有些不是。例如：
复制和切片操作通常需要线性时间（与长度有关，是O(n)时间操作）。
list和tuple的元素访问和元素赋值，是常量时间的。
dict操作的情况比较复杂，后面第8章有详细讨论。
使用组合对象的程序，需要特别考虑其中操作的复杂度。
字符串也应该看作组合对象，其许多操作不是常量时间的。
创建对象也需要付出空间和时间，空间和时间代价都与对象大小有关。对于组合对象，这里可能有需要构造的一个个元素，元素有大小问题，整体看还有元素个数问题。通常应看作线性时间和线性空间操作（以元素个数作为规模）。
在下面有关数据结构和算法的讨论中，将会介绍和分析一些Python结构和操作的效率问题。这里首先列举一些具体情况，更详细的情况见后面章节。
构造新结构，如构造新的list、set等。构造新的空结构（空表、空集合等）是常量时间操作，而构造一个包含n个元素的结构，则至少需要O(n)时间。统计说明，分配长度为n个元素的存储块的时间代价是O(n)。
一些list操作的效率：表元素访问和元素修改是常量时间操作，但一般的加入/删除元素操作（即使只加入一个元素）都是O(n)时间操作。
字典dict操作的效率：主要操作是加入新的关键码-值对和基于关键码查找关联值。它们的最坏情况复杂度是O(n)，但平均复杂度是O(1)。这是非常有趣的现象，也就是说，一般而言字典操作的效率很高，但偶然也会出现效率低的情况。
上面复杂度中的n都是有关结构中的元素个数。程序里经常用到这些操作，它们的效率对程序效率有重大影响。另外，有些操作的效率高。例如，在表的最后加入和删除元素的操作效率高，在其他地方加入和删除元素的效率低，应该优先选用前者。
空间开销
在程序里使用任何类型的对象，都需要付出空间的代价。建立一个表或者元组，至少要占用元素个数那么多空间。如果一个表的元素个数与问题规模线性相关，建立它的空间付出至少为O(n)（如果元素也是新创建的，还需考虑元素本身的存储开销）。
相对而言，表和元组是比较简单的数据结构。集合和字典需要支持快速查询等操作，其结构更加复杂。包含n个元素的集合或字典，至少需要占用O(n)的存储空间。
这里还有两个问题需要特别提出，请读者注意：
1）Python的各种组合数据对象都没有预设的最大元素个数。在实际使用中，这些结构能根据元素个数的增长自动扩充存储空间。从空间占用的角度看，其实际开销在存续期间可能变大，但通常不会自动缩小（即使后来元素变得很少了）。举个例子，假设程序里建了一个表，而后不断加入元素导致表变得很大，而后又不断删除元素，后来表中元素变得很少，但占用的存储空间并不减少。
2）还应该注意Python自动存储管理系统的影响。举个例子：如果在程序里建立了一个表，此后一直将其作为某个全局变量的值，这个对象就会始终存在并占用存储空间。如果将其作为某个函数里局部变量的值，或者虽然作为全局变量的值，但后来通过赋值将其抛弃，这个表对象就可以被回收。
总之，在估计Python程序的空间开销时，上面这些细节也需要考虑。
Python语言提供了很多高级结构，使人很容易通过简短的程序完成很多工作，例如很容易构造出新的表或元组。这种方便性有时也会带来负面作用。懒散而且不警觉的编程者很容易写出一些貌似正确但实际上完全不能用的程序，其时间开销太大而且毫无必要，使程序只能处理很小的实例，基本上不能使用；或者空间开销太大，生成大量不必要的数据对象，直至用完了可用内存，导致程序崩溃。另一个显然的事实是，构造大量数据对象本身也需要时间，这两方面的问题往往是纠缠在一起的。
今后写程序要特别关注这些问题，应该关注程序的空间和时间开销。
Python程序的时间复杂度实例
现在考虑一个很简单的例子。假设需要把得到的一系列数据存入一个表，其中得到一个数据是O(1)常量时间操作。代码可以写为：
data=[]
while还有数据:

x = 下一数据
　　 data.insert(0,x)#把新数据加在表的最前面

或者写为：

data=[]
while还有数据:
 　　x = 下一数据
　 　data.insert(len(data),x) # 新数据加在最后，或写data.append(x)

前一代码段把新元素加在已有元素之前，后一写法把新元素加在已有元素之后。两种写法都完成了所需工作，虽然产生的结果表里元素的顺序不同。现在的问题是，这两种写法的效率怎样？这个效率应该与表的结构和操作的实现方式有关。
显然这两个程序段的时间代价与循环的次数（表的最终长度）有关。但实际情况是：前一程序段需要O(n2)的时间才能完成工作，而后一个程序段只需要O(n)时间。造成这种情况与list的实现方式有关，第3章将介绍有关情况。
作为另一个例子，考虑建立一个表，其中包含从0到10000×n－1的整数值，下面几个函数都能完成这一工作：

def test1(n):
    lst=[]
    for i in range(n*10000):
        lst = lst + [i]
    return lst

def test2(n):
    lst=[]
    for i in range(n*10000):
        lst.append(i)
    return lst

def test3(n):
    return [i for i in range(n*10000)]

def test4(n):
    return list(range(n*10000))

还可能有许多其他做法也能完成这一工作。请读者自己做些试验，看看不同函数定义产生的计算代价随n的值而增长的趋势。
程序实现和效率陷阱
设计一个算法，通过对它的分析可能得到抽象算法的时间与空间复杂度。进而，采用某个编程语言（例如Python）可以做出该算法的实现。这样就出现了一个问题：算法的实现（程序）的时间开销与原算法的时间复杂度之间有什么关系？
理想的情况应该是这样：作为算法的实现，相应程序的时间开销增长趋势应该达到原算法的时间复杂度。但是，如果实现做得不好，假设原算法的时间复杂度是O(n)，其实现程序也可能比这差，例如达到O(n2)或者更差。这个讨论是想说明了一个问题，即在考虑程序的开发时，不但要选择好的算法，还要考虑如何做出算法的良好实现。
应该特别指出，用Python等高级语言编写程序存在一些“效率陷阱”，这种陷阱有可能使原本可以用计算机做的事情变得不可行（时间代价太大），或者至少也浪费了计算机和人的大量时间。在实际工作中，这种实现方式方面的（效率）缺陷很可能葬送掉一个软件，至少也会损害其可用性（降低其价值）。
上面的Python程序中就有这样的例子，例如函数test1。最常见的错误做法就是毫无必要地构造一些可能很大的复杂结构。例如在递归定义的函数里的递归调用中构造复杂的结构（如list等），而后只使用其中的个别元素。从局部看，这样做使得常量时间的操作变成了线性时间操作。但从递归算法的全局看，这种做法经常会使多项式时间算法变成指数时间算法，也就是说，把原来有用的算法变成了基本无用的算法。
这种事例也说明了一个情况：Python这样的编程系统提供了许多非常有用的高级功能，但是要想有效地使用它们，有必要了解数据结构的一些深入情况。本书的一个目标就是提供这方面的基本知识，帮助读者理解Python语言本身。
另外，有些读者也可能有非常兴趣知道Python这样强大的系统是如何构造起来的。本书也会提供一些这方面的基本信息。