数据结构：Python语言描述
1.3 算法概述 1.3.1 什么是算法
算法是解决特定问题的步骤的描述。它是有限的指令序列，其中每条指令代表一个或多个操作。
算法应具有以下五个重要特征。
(1)有限性：算法对任意合法输入执行有限步后必然结束，并且每一步都可以在有限时间内完成。
(2)确定性：算法中的每条指令都必须有准确的含义，不得有二义性，并且在任何条件下，算法的任何执行路径都是唯一的，即对于相同的输入得到的输出相同。
(3)可行性：算法是可行的，是指算法中描述的操作可以通过基本操作执行有限次数的操作来实现。
(4) 输入：算法有零个或多个输入，这些输入取自特定对象的集合。
(5)输出：算法有零个或多个输出，这些输出是与输入有某种特定关系的量。
注意：算法和程序是不同的。程序是指使用某种计算机语言对算法的具体实现，即程序具体描述了如何做，而算法则侧重于描述解决问题的方法。
使用计算机解决实际问题时，我们不仅要选择合适的数据结构，还要有好的算法。那么我们应该如何评价一个算法的好坏呢？通常通过以下指标来衡量。
(1)正确性：要求算法正确执行并满足预设的功能和性能要求，大致分为以下四个级别。
①程序不存在语法错误。
②程序可以对多组输入数据得到满足要求的结果。
③对于精心挑选的典型、严酷、困难的输入数据集，程序可以获得满足要求的结果。
④对于所有合法的输入数据，程序都能得到满足要求的结果。
（2）可读性：算法主要供人阅读和交流，其次供计算机执行。只有当算法具有可读性时，才更容易被人们理解，只有这样，人们才能调试程序并发现错误。接下来是提高编程可读性的几种方法。
①注释：在程序中添加注释不仅可以帮助程序设计者阅读和检查错误，也可以使后续维护人员更容易理解程序。
②变量命名：越复杂的程序通常涉及更多的变量命名。这时要合理设计变量的名称，以方便后续使用变量。
(3)鲁棒性：当输入数据非法或运行环境发生变化时，算法能够做出适当的响应或处理，而不是产生莫名其妙的输出结果。
(4)时间复杂度：衡量算法执行效率的指标。
(5)空间复杂度：是指算法在执行过程中所占用存储空间的度量。
1.3.2 算法的时间复杂度
算法的执行时间是根据基于该算法编写的程序在计算机上执行所需的时间来计算的。通常有两种方法。
(1)事后统计法：由于许多计算机都具有精确的计时功能，可以根据某种算法编写的程序在计算机上执行，从而计算出该算法的执行时间。不过，这个时间与所使用的编程语言，以及计算机软硬件等环境因素有关。有时很容易掩盖算法本身的优缺点，所以很少使用。
(2)预分析估算法：用高级编程语言编写的程序在计算机上运行所需的时间取决于以下因素。
①算法应该选择哪种策略？
②问题的规模。
③所使用的编程语言，对于相同的算法，语言的级别越高，执行效率越低。
④编译后的程序生成的机器码的质量。
⑤机器执行指令的速度。
从以上因素可以看出，用绝对时间单位来衡量算法的效率是不合理的。因此，我们抛开所使用的编程语言、计算机软硬件等环境因素，只考虑算法本身的效率。也就是说，认为某个算法的执行时间仅取决于问题的大小，或者是问题大小的函数。在下面的介绍中，主要采用事前分析估计的方法来分析算法的时间性能。
算法通常由控制结构（序列、分支、循环三种）和原语操作（指固有数据类型的操作）组成。例如，在算法1-1中，第6、8、9行对应的操作是原始操作。
算法1-1 原始操作
因此，算法的执行时间取决于控制结构和原始操作的综合效果。为了便于计算算法执行时间，我们从算法中选择一个作为所研究问题的基本操作的原语操作，并根据该操作重复的次数来计算其执行时间。
假设问题规模为n，对应的函数关系记为T(n)，则算法的执行时间大致等于执行基本操作所需的时间×T(n)。通常执行基本操作所需的时间是某个值，因此T(n)与算法的执行时间成正比。然后通过比较不同算法的T(n)的大小，我们可以得到不同算法的优缺点。 。接下来我们以算法1-2为例给出求解T(n)的过程。
算法1-2 矩阵加法函数
上面第5行到第7行代码是算法的可执行语句。第5行代码中的i由0变为n，因此重复次数为n+1，但对应的循环体只执行了n次；同样，第6行代码本身的重复次数也是n+1，对应的循环体只执行了n次。但是，由于嵌套在第5行代码中，因此第6行代码总共重复了n(n+1)次。同理，第7行代码重复的次数为n2。
综上所述，算法1-2的T(n)可以用下式表示。
T(n)=n+1+n(n+1)+n2=2n2+2n+1
由于上述计算的算法执行时间并不是算法的绝对执行时间，因此算法的执行时间通常进一步用T(n)的数量级来表示，记为T(n)=O( f(n))（其中 O 是 Order 的缩写）。具体含义是，存在正常数和N（N是足够大的正整数），使得
成立，从这个方程可以看出，当n足够大时，T(n)和f(n)的增长率是相同的，所以我们称O(f(n))为算法的渐近时间复杂度，简称算法的时间复杂度。
T(n)对应的f(n)可能有多个。通常只找到T(n)的最高阶，而忽略其低阶项、系数和常数项。例如，对于T(n)=n+1+n(n+1)+n2=2n2+2n+1=O(n2)，算法1-2的时间复杂度为O(n2)。
一般来说，如果算法中没有循环，则算法的时间复杂度是恒定的；如果算法中只有单个循环，则决定算法时间复杂度的基本操作就是算法中循环中语句对应的基本操作；如果算法中存在多个循环，那么决定算法时间复杂度的基本操作就是算法中循环嵌套层数最多的语句对应的基本操作的重复次数。
(1)算法中没有循环。算法1-3中没有循环，因此该算法的时间复杂度为O(1)，称为常阶。
没有循环的算法1-3
(2) 该算法包含单个循环。算法1-4包含一个循环，变量i从0变为n，第6行的基本操作被执行n次。因此，该算法的时间复杂度为O(n)，称为线性阶。
算法1-4 单循环
(3)算法包含多个循环。这里以双循环为例。算法1-5存在双循环。外循环变量i从0变为n，内循环变量j从0变为n。因此，第7行的基本操作执行了n2次，即算法的时间复杂度为O(n2)，称为平方阶。
算法1-5 双循环
另外，对于有输入的算法，其时间复杂度还与输入数据集（一个或多个输入）有关。因为对于不同的输入数据集，算法的基本操作重复的次数可能不同，即算法的时间复杂度也可能不同。
对于一个有输入的算法，如果输入不同的数据集时，基本操作重复次数最少，那么我们称此时对应的时间复杂度为该算法的最佳时间复杂度。相反，如果基本操作重复次数最多，则称为该算法的最差时间复杂度。在实际应用中，我们在等概率的前提下考虑算法的平均时间复杂度。
接下来结合具体例子给出了算法的最佳、最差和平均时间复杂度的分析计算过程。
[例1-1] 列表List 包含n 个数据。算法1-6用于查找List中前i（1≤i≤n）个数据中最大的数据。请分析该算法的最佳、最差和平均时间复杂度。
算法1-6 求n个数据中第i个的最大值
第 i 个数据是 List[0,i-1]。要返回最大的数据，需要进行 i-1 次比较。因为1≤i≤n，总共有n种情况。在每种情况的概率相等（即都是1/n）的前提下，我们可以知道
因此该算法的平均时间复杂度为O(n)。
当需要第一数据的最大值，即i=1时，不需要执行第9行的基本操作。此时相应算法的最佳时间复杂度为O(1)。
当需要获取前n个数据的最大值，即i=n时，第9行的基本操作需要执行n-1次。此时，相应算法的最差时间复杂度为O(n)。
1.3.3 算法的空间复杂度
与算法的时间复杂度类似，算法的空间复杂度一般被认为是问题规模n的函数，并以数量级的形式给出，表示为
S(n)=O(g(n))
基于算法编写的程序在计算机运行时占用的存储空间包括以下几部分：输入数据占用的存储空间、程序本身占用的存储空间以及临时变量占用的存储空间。在研究算法的空间复杂度时，仅分析临时变量占用的存储空间。例如，算法1-7中，不计算形参List占用的空间，只计算临时变量i和sum占用的存储空间。因此，该算法的空间复杂度为O(1)。
算法1-7 被调用的函数
为什么在分析算法的空间复杂度时只考虑临时变量占用的存储空间而不考虑形参占用的存储空间？让我们看看算法1-8。
算法1-8 调用的函数
算法1-8为列表List分配存储空间，在代码第6行，我们可以看到它调用了算法1-7中的Sum()函数。如果在算法1-7中，我们再次考虑形参List所占用的存储空间，那么它所占用的存储空间就会被重复计算。
从上面的例子可以看出，在分析算法的空间复杂度时，我们只需要考虑临时变量占用的存储空间，而不需要考虑形参占用的存储空间。