Python 数据结构和算法实用指南（一）（4）

Python 数据结构和算法实用指南（一）（3）https://developer.aliyun.com/article/1507529

第三章：算法设计原则

我们为什么要学习算法设计？当然有很多原因，我们学习某些东西的动机很大程度上取决于我们自己的情况。对于对算法设计感兴趣有重要专业原因。算法是所有计算的基础。我们可以将计算机视为一台硬件，带有硬盘、内存芯片、处理器等。然而，如果缺少的是算法，现代技术将不可能存在。让我们在接下来的章节中了解更多。

在本章中，我们将讨论以下主题：

• 算法简介
  
• 递归和回溯
  
• 大 O 符号
  

技术要求

我们需要使用 Python 安装matplotlib库来绘制本章的图表。

可以通过在终端上运行以下命令在 Ubuntu/Linux 上安装：

python3 -mpip install matplotlib

您还可以使用以下内容：

sudo apt-get install python3-matplotlib 

在 Windows 上安装matplotlib：

如果 Python 已经安装在 Windows 操作系统上，可以从以下链接获取matplotlib并在 Windows 上安装：github.com/matplotlib/matplotlib/downloads 或 matplotlib.org。

本章的代码文件可以在以下链接找到：github.com/PacktPublishing/Hands-On-Data-Structures-and-Algorithms-with-Python-Second-Edition/tree/master/Chapter03。

算法简介

算法的理论基础，以图灵机的形式，是在数字逻辑电路实际上能够实现这样的机器的几十年前建立的。图灵机本质上是一个数学模型，它使用预定义的一组规则，将一组输入转换为一组输出。图灵机的第一批实现是机械的，下一代可能会看到数字逻辑电路被量子电路或类似的东西所取代。无论平台如何，算法都起着中心主导作用。

算法对技术创新的影响是另一个方面。显而易见的例子是页面排名搜索算法，Google 搜索引擎就是基于其变体。使用这些和类似的算法允许研究人员、科学家、技术人员等快速搜索大量信息。这对新研究的速度、新发现的速度以及新的创新技术的开发速度产生了巨大影响。算法是执行特定任务的顺序指令集。它们非常重要，因为我们可以将一个复杂的问题分解为一个小问题，以准备执行一个大问题的简单步骤——这是算法最重要的部分。一个好的算法是解决特定问题的高效程序的关键。学习算法也很重要，因为它训练我们对某些问题进行非常具体的思考。它可以通过隔离问题的组成部分并定义这些组成部分之间的关系来增加我们的问题解决能力。总之，学习算法有一些重要原因：

• 它们对计算机科学和智能系统至关重要
  
• 它们在许多其他领域中很重要（计算生物学、经济学、生态学、通信、生态学、物理等）
  
• 它们在技术创新中发挥作用
  
• 它们改进问题解决和分析思维
  

解决给定问题主要有两个重要方面。首先，我们需要一个有效的机制来存储、管理和检索数据，这对解决问题很重要（这属于数据结构）；其次，我们需要一个有效的算法，这是一组有限的指令来解决问题。因此，研究数据结构和算法对使用计算机程序解决任何问题至关重要。有效的算法应具有以下特征：

• 它应该尽可能具体
  
• 算法的每个指令都应该被正确定义
  
• 不应该有任何模糊的指令
  
• 算法的所有指令都应该在有限的时间内和有限的步骤内可执行
  
• 它应该有清晰的输入和输出来解决问题
  
• 算法的每个指令在解决给定问题时都很重要
  

算法在其最简单的形式中只是一系列操作 - 一系列指令。它可能只是一个形式为 do x，然后 do y，然后 do z，然后完成的线性构造。然而，为了使事情更有用，我们添加了类似于 do x然后 do y的子句；在 Python 中，这些是 if-else 语句。在这里，未来的行动取决于某些条件；比如数据结构的状态。为此，我们还添加了操作、迭代、while 和 for 语句。扩展我们的算法素养，我们添加了递归。递归通常可以实现与迭代相同的结果，但它们在根本上是不同的。递归函数调用自身，将相同的函数应用于逐渐减小的输入。任何递归步骤的输入是前一个递归步骤的输出。

算法设计范式

一般来说，我们可以分辨出三种算法设计的广泛方法。它们是：

• 分而治之
  
• 贪婪算法
  
• 动态规划
  

正如其名称所示，分而治之范式涉及将问题分解为较小的简单子问题，然后解决这些子问题，最后将结果组合以获得全局最优解。这是一种非常常见和自然的问题解决技术，可以说是算法设计中最常用的方法。例如，归并排序是一种对 n 个自然数列表进行递增排序的算法。

在这个算法中，我们迭代地将列表分成相等的部分，直到每个子列表包含一个元素，然后我们将这些子列表组合在一起，以排序顺序创建一个新列表。我们将在本节/章节后面更详细地讨论归并排序。

分而治之算法范式的一些例子如下：

• 二分搜索
  
• 归并排序
  
• 快速排序
  
• Karatsuba 算法用于快速乘法
  
• 斯特拉森矩阵乘法
  
• 最接近的点对
  

贪婪算法通常涉及优化和组合问题。在贪婪算法中，目标是在每一步中从许多可能的解决方案中获得最佳的最优解，并且我们试图获得局部最优解，这可能最终导致我们获得整体最优解。通常，贪婪算法用于优化问题。以下是许多流行的标准问题，我们可以使用贪婪算法来获得最优解：

• 克鲁斯卡尔最小生成树
  
• 迪杰斯特拉最短路径
  
• 背包问题
  
• 普林姆最小生成树算法
  
• 旅行推销员问题
  

贪婪算法通常涉及优化和组合问题；经典的例子是将贪婪算法应用于旅行推销员问题，其中贪婪方法总是首先选择最近的目的地。这种最短路径策略涉及找到局部问题的最佳解决方案，希望这将导致全局解决方案。

另一个经典的例子是将贪婪算法应用于旅行推销员问题；这是一个 NP 难问题。在这个问题中，贪婪方法总是首先选择当前城市中最近的未访问城市；这样，我们不能确定我们得到了最佳解决方案，但我们肯定得到了一个最优解。这种最短路径策略涉及在希望这将导致全局解决方案的情况下找到局部问题的最佳解决方案。

动态规划方法在我们的子问题重叠时非常有用。这与分治法不同。与将问题分解为独立子问题不同，动态规划中间结果被缓存并可以在后续操作中使用。与分治法一样，它使用递归；然而，动态规划允许我们在不同阶段比较结果。这对于某些问题来说可能比分治法具有性能优势，因为通常从内存中检索先前计算的结果比重新计算要快。动态规划也使用递归来解决问题。例如，矩阵链乘法问题可以使用动态规划来解决。矩阵链乘法问题确定了在给定一系列矩阵时，最有效的矩阵相乘的顺序，它找到需要最少操作次数的乘法顺序。

例如，让我们看看三个矩阵——P、Q和R。要计算这三个矩阵的乘法，我们有许多可能的选择（因为矩阵乘法是可结合的），比如*(PQ)R = P(QR)。因此，如果这些矩阵的大小是——P是 20×30，Q是 30×45，R是 45×50，那么(PQ)R和P(QR)*的乘法次数将是：

• (PQ)R = 20 x 30 x 45 + 20 x 45 x 50 = 72,000
  
• P(QR) = 20 x 30 x 50 + 30 x 45 x 50 = 97,500
  

从这个例子可以看出，如果我们使用第一个选项进行乘法，那么我们需要 72,000 次乘法，与第二个选项相比要少。这在以下代码中显示：

def MatrixChain(mat, i, j):   
    if i == j:   
        return 0   
    minimum_computations = sys.maxsize  
    for k in range(i, j): 
        count = (MatrixChain(mat, i, k) + MatrixChain(mat, k+1, j)+ mat[i-1] * mat[k] * mat[j])   
        if count < minimum_computations:  
              minimum_computations= count;    
        return minimum_computations;  
matrix_sizes = [20, 30, 45, 50];  
print("Minimum multiplications are", MatrixChain(matrix_sizes , 1, len(matrix_sizes)-1));
#prints 72000

第十三章，设计技术和策略，对算法设计策略进行了更详细的讨论。

递归和回溯

递归对于分治问题特别有用；然而，确切地了解发生了什么可能很困难，因为每个递归调用本身都会产生其他递归调用。递归函数可能会陷入无限循环，因此需要每个递归函数都遵守一些属性。递归函数的核心是两种类型的情况：

• 基本情况：这些告诉递归何时终止，意味着一旦满足基本条件，递归将停止
  
• 递归情况：函数调用自身，我们朝着实现基本条件的目标前进
  

一个自然适合递归解决方案的简单问题是计算阶乘。递归阶乘算法定义了两种情况：当n为零时的基本情况（终止条件），以及当n大于零时的递归情况（函数本身的调用）。一个典型的实现如下：

def factorial(n): 
    # test for a base case      
    if  n==0: 
        return 1 
        #make a calculation and a recursive call
    else: 
        f= n*factorial(n-1) 
    print(f) 
    return(f) 
factorial(4)

要计算4的阶乘，我们需要四次递归调用加上初始父调用。在每次递归中，方法变量的副本都存储在内存中。一旦方法返回，它就会从内存中删除。以下是我们可以可视化这个过程的一种方式：

递归或迭代哪个更好的解决方案可能并不清楚；毕竟，它们都重复一系列操作，并且都非常适合分治方法和算法设计。迭代一直进行，直到问题解决为止。递归将问题分解成越来越小的块，然后将结果组合起来。迭代对程序员来说通常更容易，因为控制保持在循环内部，而递归可以更接近表示阶乘等数学概念。递归调用存储在内存中，而迭代不是。这在处理器周期和内存使用之间产生了一种权衡，因此选择使用哪种可能取决于任务是处理器密集型还是内存密集型。以下表格概述了递归和迭代之间的主要区别：

回溯

回溯是一种特别适用于遍历树结构等类型问题的递归形式，其中对于每个节点我们有许多选项可供选择。随后，我们会得到一组不同的选项，根据所做的选择系列，会达到一个目标状态或者一个死胡同。如果是后者，我们必须回溯到先前的节点并遍历不同的分支。回溯是一种用于穷举搜索的分治方法。重要的是，回溯修剪了无法给出结果的分支。

下面给出了回溯的一个例子。在这里，我们使用了递归方法来生成给定字符串 s 的所有可能排列，长度为 n：

def bitStr(n,s):
 if n==1: return s 
 return [digit + bits for digit in bitStr(1,s) for bits in bitStr(n-1,s)] 
print(bitStr(3,'abc'))

这产生了以下输出：

注意这个推导中的双重列表压缩和两个递归调用。这递归地连接了初始序列的每个元素，当 n =1 时返回，与先前递归调用生成的字符串的每个元素。在这个意义上，它是 回溯，以揭示先前未生成的组合。返回的最终字符串是初始字符串的所有 n 个字母组合。

分治——长乘法

为了使递归不仅仅是一个巧妙的技巧，我们需要了解如何将其与其他方法进行比较，例如迭代，并了解何时使用它将导致更快的算法。我们都熟悉的迭代算法是我们在小学数学课上学到的程序，用于将两个大数相乘。那就是长乘法。如果你记得的话，长乘法涉及迭代乘法和进位操作，然后是移位和加法操作。

我们的目标是检查如何衡量这个过程的效率，并尝试回答这个问题——这是我们用来将两个大数相乘的最有效的过程吗？

在下图中，我们可以看到将两个四位数相乘需要 16 次乘法运算，我们可以概括地说，一个 n 位数需要大约 n^(2) 次乘法运算：

以计算原语的数量，如乘法和加法，来分析算法的方法很重要，因为它为我们提供了一种理解完成某个计算所需的时间与该计算的输入大小之间关系的方法。特别是，我们想知道当输入，即数字的位数n非常大时会发生什么。这个主题被称为渐近分析或时间复杂度，对我们研究算法至关重要，在本章和本书的其余部分我们将经常回顾这个主题。

递归方法

事实证明，在长乘法的情况下，答案是肯定的，实际上有几种算法可以减少操作次数。其中最著名的替代长乘法的算法之一是Karatsuba 算法，首次发表于 1962 年。这采用了一种基本不同的方法：而不是迭代地相乘单个数字，它在逐渐减小的输入上递归地进行乘法运算。递归程序在输入的较小子集上调用自身。构建递归算法的第一步是将一个大数分解为几个较小的数。这样做的最自然的方式是将数字分成两半，前半部分是最高有效数字，后半部分是最低有效数字。例如，我们的四位数 2345 变成了一对两位数 23 和 45。我们可以使用以下更一般的分解来写出任意两个n位数x和y的分解，其中m是小于n的任意正整数：

！

！

现在我们可以将我们的乘法问题x，y重写如下：

！

当我们展开时，我们得到以下结果：

！

更方便的是，我们可以这样写（方程 3.1）：

！ … (3.1)

在哪里：

！

应该指出，这表明了一种递归方法来乘两个数字，因为这个过程本身涉及乘法。具体来说，乘积ac、ad、bc和bd都涉及比输入数字小的数字，因此我们可以将相同的操作应用为整体问题的部分解决方案。到目前为止，这个算法包括四个递归乘法步骤，目前还不清楚它是否比经典的长乘法方法更快。

到目前为止，我们所讨论的关于递归方法的乘法，自 19 世纪末以来就为数学家所熟知。Karatsuba 算法通过以下观察改进了这一点。我们实际上只需要知道三个量：z[2]= ac，z[1]=ad +bc，和z[0]= bd来解方程 3.1。我们只需要知道a、b、c和d的值，因为它们对计算涉及的总和和乘积有贡献。这表明或许我们可以减少递归步骤的数量。事实证明，情况确实如此。

由于乘积ac和bd已经处于最简形式，看来我们无法消除这些计算。然而，我们可以做出以下观察：

！

当我们减去我们在上一个递归步骤中计算的量ac和bd时，我们得到我们需要的量，即(ad + bc)：

！

这表明我们确实可以计算ad + bc的和，而不必分别计算每个单独的数量。总之，我们可以通过将四个递归步骤减少到三个来改进方程 3.1。这三个步骤如下：

1. 递归计算ac
   
2. 递归计算bd
   
3. 递归计算（a + b）（c + d）并减去ac和bd
   

以下示例展示了 Karatsuba 算法的 Python 实现。在以下代码中，最初，我们检查给定数字中是否有任何一个小于 10，然后就不需要运行递归函数。接下来，我们确定较大值的数字位数，并在数字位数为奇数时加一。最后，我们递归调用函数三次来计算ac、bd和（a + d）（c + d）。以下代码打印任意两个数字的乘积；例如，它打印出4264704来表示1234和3456的乘积。Karatsuba 算法的实现如下：

from math import log10 
def karatsuba(x,y): 
    #The base case for recursion 
    if x<10 or y<10:
        return x*y 
    #sets n, the number of digits in the highest input number
    n=max(int(log10(x)+1), int(log10(y)+1)) 
    #rounds up n/2  
    n_2 = int(math.ceil(n/2.0)) 
    #adds 1 if n is uneven  
    n = n if n%2 == 0  else n+1 
    #splits the input numbers 
    a, b = divmod(x, 10**n_2) 
    c, d = divmod(y,10**n_2) 
    #applies the three recursive steps 
    ac = karatsuba(a,c) 
    bd = karatsuba(b,d)  
    ad_bc = karatsuba((a+b),(c+d))-ac-bd 
    #performs the multiplication 
    return (((10**n)*ac)+bd+((10**n_2)*(ad_bc)))
t= karatsuba(1234,3456)
print(t)
# outputs - 4264704

运行时间分析

算法的性能通常由其输入数据的大小（n）以及算法使用的时间和内存空间来衡量。所需的时间由算法执行的关键操作（如比较操作）来衡量，而算法的空间需求则由在程序执行期间存储变量、常量和指令所需的存储空间来衡量。算法的空间需求在执行期间也可能动态变化，因为它取决于变量大小，这在运行时决定，例如动态内存分配、内存堆栈等。

算法所需的运行时间取决于输入大小；随着输入大小（n）的增加，运行时间也会增加。例如，对于输入大小为 5,000 的列表，排序算法将需要更多的运行时间来排序，而对于输入大小为 50 的列表，运行时间较短。因此，可以清楚地看出，要计算时间复杂度，输入大小是重要的。此外，对于特定输入，运行时间取决于算法中要执行的关键操作。例如，对于排序算法，关键操作是比较操作，它将占用大部分时间，而不是赋值或其他任何操作。要执行的关键操作越多，运行算法所需的时间就越长。

应该注意的是，算法设计的一个重要方面是评估效率，无论是在空间（内存）还是时间（操作次数）方面。应该提到的是，用于衡量算法内存性能的度量标准与衡量算法运行时间的度量标准相同。我们可以以多种方式来衡量运行时间，最明显的方式可能是简单地测量算法所需的总时间。这种方法的主要问题在于算法运行所需的时间非常依赖于其运行的硬件。衡量算法运行时间的一个与平台无关的方法是计算所涉及的操作次数。然而，这也是有问题的，因为没有明确的方法来量化一个操作。这取决于编程语言、编码风格以及我们决定如何计算操作。然而，如果我们将这种计算操作的想法与一个期望相结合，即随着输入大小的增加，运行时间将以特定方式增加，我们就可以使用这个想法。也就是说，输入大小n和算法运行时间之间存在数学关系。基本上有三个因素决定了算法的运行时间性能；它们可以描述如下：

• 最坏情况复杂度是上界复杂度；它是算法执行所需的最大运行时间。在这种情况下，关键操作将执行最大次数。
  
• 最佳情况复杂度是下界复杂度；这是算法执行所需的最小运行时间。在这种情况下，关键操作将执行最少次数。
  
• 平均情况复杂度是算法执行所需的平均运行时间。
  

最坏情况分析是有用的，因为它给出了我们的算法保证不会超过的严格上界。忽略小的常数因子和低阶项，实际上就是忽略那些在输入规模较大时对总运行时间没有很大贡献的事物。这不仅使我们的工作在数学上更容易，而且还使我们能够专注于对性能影响最大的事物。

我们在 Karatsuba 算法中看到，乘法操作的数量增加到输入大小n的平方。如果我们有一个四位数，乘法操作的数量是 16；一个八位数需要 64 次操作。通常，我们实际上并不关心算法在n的小值时的行为，所以我们经常忽略随着n线性增加的因子。这是因为在较大的n值时，随着n的增加，增长最快的操作将占主导地位。

我们将通过一个示例来更详细地解释这个归并排序算法。排序是第十章的主题，排序，然而，作为一个前导和了解运行时性能的有用方式，我们将在这里介绍归并排序。

归并排序算法是 60 多年前开发的经典算法。它仍然广泛应用于许多最流行的排序库中。它相对简单而高效。它是一种使用分而治之方法的递归算法。这涉及将问题分解为更小的子问题，递归地解决它们，然后以某种方式组合结果。归并排序是分而治之范式最明显的演示之一。

归并排序算法由三个简单的步骤组成：

1. 递归地对输入数组的左半部分进行排序
   
2. 递归地对输入数组的右半部分进行排序
   
3. 将两个排序好的子数组合并成一个
   

典型问题是将一组数字按数字顺序排序。归并排序通过将输入分成两半，并同时处理每一半来工作。我们可以用以下图表来形象地说明这个过程：

这是归并排序算法的 Python 代码：

def mergeSort(A): 
#base case if the input array is one or zero just return. 
if len(A) > 1: 
    # splitting input array 
    print('splitting ', A ) 
    mid=len(A)//2   
    left=A[:mid]   
    right=A[mid:] 
    #recursive calls to mergeSort for left and right subarrays 
    mergeSort(left)   
    mergeSort(right) 
    #initalizes pointers for left(i) right(j) and output array (k)
    #3 initalization operations 
    i = j = k = 0 
    #Traverse and merges the sorted arrays 
    while i < len(left) and j < len(right):  
    #if left < right comparison operation 
        if left[i] < right[j]:  
        #if left < right Assignment operation  
            A[k] = left[i]  
            i=i+1 
        else:   
            #if right <= left assignment 
            A[k]=right[j] 
            j=j+1   
            k=k+1   
    while i< len(left):   
    #Assignment operation 
        A[k] = left[i] 
        i=i+1   
        k=k+1   
    while j< len(right):   
    # Assignment operation    
        A[k] = right[j] 
        j=j+1 
        k=k+1 
print('merging',A) 
return(A)

我们运行这个程序得到以下结果：

我们感兴趣的问题是如何确定运行时性能，也就是说，算法完成所需的时间与n的大小相关的增长率是多少？为了更好地理解这一点，我们可以将每个递归调用映射到一个树结构上。树中的每个节点都是递归调用，处理逐渐变小的子问题：

每次调用归并排序都会随后创建两个递归调用，因此我们可以用二叉树来表示这一点。每个子节点都接收输入的一个子集。最终，我们想知道算法完成所需的总时间与n的大小相关。首先，我们可以计算树的每个级别的工作量和操作数量。

关注运行时分析，在第一级，问题分成两个n/2 个子问题；在第二级，有四个n/4 个子问题，依此类推。问题是，递归何时结束，也就是说，何时达到基本情况？这只是当数组要么是零要么是一时。

递归级别的数量恰好是将n除以二直到得到最多为一的数字的次数。这恰好是 log2 的定义。由于我们将初始递归调用计为级别零，总级别数为 log[2]n + 1。

让我们暂停一下，重新定义一下。到目前为止，我们一直用字母n来描述输入中的元素数量。这指的是递归的第一级中的元素数量，也就是初始输入的长度。我们需要区分后续递归级别的输入大小。为此，我们将使用字母m，或者特别是m[j]来表示递归级别j的输入长度。

此外，还有一些细节我们忽略了，我相信你也开始好奇了。例如，当m/2 不是整数时会发生什么，或者当我们的输入数组中有重复元素时会发生什么？事实证明，这对我们的分析并没有重要影响；我们将在《第十二章设计技术和策略》中重新审视归并排序算法的一些细节。

使用递归树来分析算法的优势在于我们可以计算每个递归级别的工作量。我们定义这个工作量就是总操作次数，这当然与输入的大小有关。以平台无关的方式来测量和比较算法的性能是很重要的。实际运行时间当然取决于其运行的硬件。计算操作次数很重要，因为它给了我们一个与算法性能直接相关的度量，而不受平台的影响。

一般来说，由于归并排序的每次调用都会进行两次递归调用，所以调用次数在每个级别都会翻倍。与此同时，每个调用都在处理其父级别一半大小的输入。我们可以形式化地说，在第j级，其中j是整数0, 1, 2 … log[2]n，有两个大小为n/2^j的子问题。

要计算总操作次数，我们需要知道合并两个子数组所包含的操作次数。让我们来数一下之前 Python 代码中的操作次数。我们感兴趣的是在进行两次递归调用之后的所有代码。首先，我们有三个赋值操作。然后是三个while循环。在第一个循环中，我们有一个 if-else 语句，在每个操作中，都有一个比较，然后是一个赋值。由于在 if-else 语句中只有一个这样的操作集，我们可以将这段代码计算为每次递归执行两次的操作。接下来是两个while循环，每个循环都有一个赋值操作。这使得每次归并排序递归的总操作次数为4m + 3。

由于m至少必须为一，操作次数的上限是 7m。必须指出，这并不是一个精确的数字。当然，我们可以决定以不同的方式计算操作次数。我们没有计算增量操作或任何维护操作；然而，在高值的n下，这并不重要，因为我们更关心运行时间相对于n的增长率。

这可能看起来有点令人生畏，因为每次递归调用本身都会产生更多的递归调用，似乎呈指数级增长。使这一切变得可控的关键事实是，随着递归调用次数翻倍，每个子问题的大小减半。这两股相反的力量得到了很好的抵消，我们可以证明这一点。

要计算递归树每个级别的最大操作次数，我们只需将子问题的数量乘以每个子问题的操作次数，如下所示：

重要的是，这表明，因为2^j取消了每个级别的操作数量，所以每个级别的操作数量是独立的。这给了我们每个级别执行的操作数量的上限，在这个例子中是 7n。需要指出的是，这包括在该级别上每个递归调用执行的操作数量，而不是在后续级别上进行的递归调用。这表明工作是完成的，因为随着每个级别递归调用的数量翻倍，而每个子问题的输入大小减半，这正好抵消了这一事实。

要找到完整归并排序的总操作数，我们只需将每个级别上的操作数乘以级别数。这给出了以下结果：

当我们展开这个式子时，我们得到以下结果：

从中可以得出一个关键点，即输入大小和总运行时间之间存在对数关系。如果你还记得学校数学，对数函数的显著特点是它非常快速地变平。作为输入变量，x增加，输出变量y增加的幅度越来越小。

例如，将对数函数与线性函数进行比较：

在前面的例子中，将nlog[2] n分量与进行比较：

注意，对于非常低的n值，完成时间t实际上比运行时间为 n2 的算法更低。然而，对于大约 40 以上的值，对数函数开始主导，使输出变得平坦，直到相对较中等大小的n = 100 时，性能比运行时间为n²的算法高出一倍以上。还要注意，在高n值时，常数因子+7 的消失是无关紧要的。

用于生成这些图表的代码如下：

import matplotlib.pyplotasplt 
import math   
x = list(range(1,100))   
l=[]; l2=[]; a=1   
plt.plot(x, [y*y for y in x])  
plt.plot(x, [(7*y)*math.log(y,2) for y in x]) 
plt.show()

如果尚未安装matplotlib库，您需要安装它才能运行。详细信息可以在以下地址找到；我鼓励您尝试使用列表推导表达式来生成图表。例如，我们可以添加以下plot语句：

plt.plot(x, [(6*y)* math.log(y, 2) for y in x])

这给出了以下输出：

前面的图表显示了计算六次操作或七次操作的差异。我们可以看到这两种情况的分歧，这在谈论应用程序的具体情况时很重要。然而，我们在这里更感兴趣的是一种表征增长率的方法。我们不太关心绝对值，而是关心这些值随着n的增加而如何变化。通过这种方式，我们可以看到两条较低的曲线与顶部（x²）曲线相比具有相似的增长率。我们说这两条较低的曲线具有相同的复杂度类。这是一种理解和描述不同运行时行为的方法。我们将在下一节中正式化这个性能指标。

渐近分析

算法的渐近分析是指计算算法的运行时间。要确定哪个算法更好，给定两个算法，一个简单的方法是运行两个程序，对于给定的输入，执行时间最短的算法比另一个更好。然而，可能对于特定的输入，一个算法比另一个更好，而对于算法可能表现更差的任何其他输入值。

在渐近分析中，我们比较两个算法的输入大小而不是实际运行时间，并测量随着输入大小的增加，所需时间的增加情况。这通过以下代码表示：

# Linear search program to search an element, return the index position of the #array
def searching(search_arr, x):     
    for i in range(len(search_arr)):         
        if search_arr [i] == x:             
                return i     
    return -1
search_ar= [3, 4, 1, 6, 14]
x=4
searching(search_ar, x)
print("Index position for the element x is :",searching(search_ar, x))
#outputs index position of the element x that is - 1

假设数组的大小为n，*T(n)*是执行线性搜索所需的关键操作总数，这个例子中的关键操作是比较。让我们以线性搜索为例来理解最坏情况、平均情况和最佳情况的复杂性：

• 最坏情况分析：我们考虑上界运行时间，即算法所需的最长时间。在线性搜索中，最坏情况发生在要搜索的元素在最后一次比较中被找到或者在列表中未找到。在这种情况下，将会有最大数量的比较，即数组中的元素总数。因此，最坏情况的时间复杂度是Θ(n)。
  
• 平均情况分析：在这种分析中，我们考虑元素可能在列表中被找到的所有可能情况，然后计算平均运行时间复杂度。例如，在线性搜索中，如果要搜索的元素在0索引处找到，那么所有位置的比较次数将为1，类似地，对于在1, 2, 3, … (n-1)索引位置找到的元素，比较次数将分别为 2, 3，直到n。因此，平均时间复杂度可以定义为average-case complexity= (1+2+3…n)/n = n(n+1)/2。
  
• 最佳情况分析：最佳情况的运行时间复杂度是算法运行所需的最短时间；它是下界运行时间。在线性搜索中，最佳情况是要搜索的元素在第一次比较中被找到。在这个例子中，很明显最佳情况的时间复杂度不取决于列表的长度。因此，最佳情况的时间复杂度将是Θ(1)。
  

通常，我们使用最坏情况分析来分析算法，因为它为我们提供了运行时间的上界，而最佳情况分析是最不重要的，因为它为我们提供了算法所需的最小时间的下界。此外，计算平均情况分析非常困难。

为了计算这些情况，我们需要知道上界和下界。我们已经看到了用数学表达式表示算法运行时间的方法，基本上是添加和乘法操作。使用渐近分析，我们只需创建两个表达式，分别用于最佳和最坏情况。

大 O 符号

大 O 符号中的 O 代表 order，意味着增长率被定义为函数的阶。它衡量最坏情况的运行时间复杂度，即算法所需的最长时间。我们说一个函数T(n)是另一个函数F(n)的大 O，我们定义如下：

输入大小n的函数g(n)基于这样的观察：对于所有足够大的n值，g(n)都受到f(n)的常数倍的上界限制。目标是找到小于或等于f(n)的增长率最小的增长率。我们只关心在较高的n值发生的情况。变量n**0表示增长率不重要的阈值以下。函数T(n)表示紧密上界F(n)。在下图中，我们可以看到T(n) = n^(2) + 500 = O(n^(2))，其中C = 2，n[0]约为 23：

您还会看到符号f(n) = O(g(n))。这描述了O(g(n))实际上是一个包含所有增长速度与f(n)相同或更小的函数的集合。例如，O(n^(2))也包括函数O(n)，*O(nlogn)*等。让我们考虑另一个例子。

函数f(x)= 19n log[2]n +56 的大 O 时间复杂度为O(nlogn)。

在下表中，我们按照从低到高的顺序列出了最常见的增长率。我们有时将这些增长率称为函数的时间复杂度或函数的复杂度类：

组合复杂度类

通常，我们需要找到一系列基本操作的总运行时间。事实证明，我们可以组合简单操作的复杂度类来找到更复杂的组合操作的复杂度类。目标是分析函数或方法中的组合语句，以了解执行多个操作的总时间复杂度。组合两个复杂度类的最简单方法是将它们相加。当我们有两个连续的操作时就会发生这种情况。例如，考虑将元素插入列表然后对该列表进行排序的两个操作。我们可以看到插入项目需要O(n)时间，排序需要O(nlogn)时间。我们可以将总时间复杂度写为O(n + nlogn)，也就是说，我们将两个函数放在O(…)中。我们只对最高阶项感兴趣，因此这让我们只剩下O(nlogn)。

如果我们重复一个操作，例如在while循环中，那么我们将复杂度类乘以操作执行的次数。如果一个时间复杂度为*O(f(n))的操作重复执行O(n)*次，那么我们将两个复杂度相乘：

例如，假设函数f(...)的时间复杂度为O(n²)，并且在while循环中执行了n次，如下所示：

for i in range(n): 
        f(...)

然后，这个循环的时间复杂度变为O(n²) * O(n) = O(n * n²) = O(n³)。在这里，我们只是将操作的时间复杂度乘以这个操作执行的次数。循环的运行时间最多是循环内部语句的运行时间乘以迭代次数。一个单独的嵌套循环，也就是一个循环嵌套在另一个循环中，假设两个循环都运行 n 次，将在 n²时间内运行，就像下面的例子中演示的那样：

for i in range(0,n): 
    for j in range(0,n)  
            #statements

每个语句都是一个常数c，执行nn次，因此我们可以将运行时间表示为以下形式：

对于嵌套循环中的连续语句，我们将每个语句的时间复杂度相加，然后乘以语句执行的次数，例如：

n=500  #c0 
#executes n times  
for i in range(0,n):  
    print(i)    #c1
   #executes n times   
for i in range(0,n):  
#executes n times  
    for j in range(0,n):  
            print(j)  #c2

这可以写成c[0] +c[1 ]n + cn^(2 )= O(n²)。

我们可以定义（以 2 为底）对数复杂度，将问题的大小减少一半，以常数时间。例如，考虑以下代码片段：

i=1   
while i<=n: 
    i=i*2 
    print(i)   

注意 i 在每次迭代时都会加倍；如果我们以n=10 运行它，我们会看到它打印出四个数字：2，4，8 和 16。如果我们将n加倍，我们会看到它打印出五个数字。随着n的每次加倍，迭代次数只增加了一个。如果我们假设k次迭代，我们可以将其写成如下形式：

由此可得，总时间 = O(log(n))。

尽管大 O 符号是渐近分析中最常用的符号，但还有两个相关的符号应该简要提到。它们是 Omega 符号和 Theta 符号。

Omega 符号（Ω）

Omega 符号描述了算法的严格下界，类似于大 O 符号描述了严格的上界。Omega 符号计算算法的最佳运行时间复杂度。它提供了最高的增长率T(n)，它小于或等于给定算法。它可以计算如下：

Theta 符号（ϴ）

通常情况下，给定函数的上界和下界是相同的，Theta 符号的目的是确定是否是这种情况。定义如下：

尽管 Omega 和 Theta 符号需要完全描述增长率，但最实用的是大 O 符号，这是你经常看到的符号。

摊销分析

通常我们对单个操作的时间复杂度不太感兴趣；我们更关心操作序列的平均运行时间。这就是摊销分析。它与平均情况分析不同，我们将很快讨论，因为我们对输入值的数据分布没有任何假设。然而，它考虑了数据结构的状态变化。例如，如果列表已排序，则任何后续的查找操作应该更快。摊销分析考虑了数据结构的状态变化，因为它分析操作序列，而不仅仅是聚合单个操作。

摊销分析描述了算法运行时间的上界；它对算法中的每个操作施加了额外的成本。序列的额外考虑成本可能比初始昂贵的操作要便宜。

当我们有少量昂贵的操作，比如排序，和大量更便宜的操作，比如查找时，标准的最坏情况分析可能会导致过于悲观的结果，因为它假设每次查找都必须比较列表中的每个元素直到找到匹配项。我们应该考虑到一旦我们对列表进行排序，我们可以使后续的查找操作变得更便宜。

到目前为止，在我们的运行时分析中，我们假设输入数据是完全随机的，并且只关注输入大小对运行时间的影响。算法分析还有另外两种常见的方法，它们是：

• 平均情况分析
  
• 基准测试
  

平均情况分析将找到基于对各种输入值的相对频率的一些假设的平均运行时间。使用真实世界的数据，或者复制真实世界数据的分布的数据，往往是基于特定数据分布的，然后计算平均运行时间。

基准测试就是简单地有一组约定的典型输入，用于衡量性能。基准测试和平均时间分析都依赖于一些领域知识。我们需要知道典型或预期的数据集是什么。最终，我们将尝试通过微调到一个非常特定的应用设置来提高性能。

让我们看一种简单的方法来衡量算法的运行时间性能。这可以通过简单地计时算法完成给定各种输入大小所需的时间来完成。正如我们之前提到的，这种衡量运行时间性能的方式取决于它运行的硬件。显然，更快的处理器会给出更好的结果，然而，随着输入大小的增加，它们的相对增长率将保留算法本身的特征，而不是运行在硬件上。绝对时间值将在硬件（和软件）平台之间有所不同；然而，它们的相对增长仍将受到算法的时间复杂度的限制。

让我们以一个嵌套循环的简单例子来说明。很明显，这个算法的时间复杂度是O(n²)，因为在外部循环的每个n次迭代中，内部循环也有n次迭代。例如，我们简单的嵌套 for 循环包含在内部循环中执行的一个简单语句：

def nest(n):   
for i in range(n):   
     for j in range(n):  
            i+j

以下代码是一个简单的测试函数，它使用不断增加的n值运行nest函数。在每次迭代中，我们使用timeit.timeit函数计算这个函数完成所需的时间。timeit函数在这个例子中接受三个参数，一个表示要计时的函数的字符串表示，一个导入nest函数的setup函数，以及一个int参数，表示执行主语句的次数。

由于我们对nest函数完成所需的时间与输入大小n感兴趣，对于我们的目的来说，每次迭代调用nest函数一次就足够了。以下函数返回每个n值的计算运行时间的列表：

import timeit 
def test2(n): 
    ls=[]   
    for n in range(n):
        t=timeit.timeit("nest(" + str(n) + ")", setup="from _main_ import nest", number=1)  
        ls.append(t) 
    return ls

在下面的代码中，我们运行test2函数并绘制结果，以及适当缩放的n²函数进行比较，用虚线表示：

import matplotlib.pyplot as plt 
n=1000 
plt.plot(test2(n)) 
plt.plot([x*x/10000000 for x in range(n)])

这给出了以下结果：

正如我们所看到的，这基本上符合我们的预期。应该记住，这既代表了算法本身的性能，也代表了底层软件和硬件平台的行为，正如测量运行时间的变化和运行时间的相对大小所指示的那样。显然，更快的处理器会导致更快的运行时间，而且性能也会受到其他运行进程、内存限制、时钟速度等的影响。

总结

在本章中，我们已经对算法设计进行了一般性概述。重要的是，我们研究了一种独立于平台的算法性能衡量方法。我们研究了一些不同的算法问题解决方法。我们研究了一种递归相乘大数的方法，也研究了归并排序的递归方法。我们学习了如何使用回溯进行穷举搜索和生成字符串。我们还介绍了基准测试的概念以及一种简单的依赖于平台的衡量运行时间的方法。

在接下来的章节中，我们将参考特定的数据结构重新讨论这些想法。在下一章中，我们将讨论链表和其他指针结构。