每个程序员都应该知道的 40 个算法（一）（1）

原文：zh.annas-archive.org/md5/8ddea683d78e7bd756401ec665273969

译者：飞龙

协议：CC BY-NC-SA 4.0

前言

算法在计算机科学和实践中一直扮演着重要角色。本书侧重于利用这些算法来解决现实世界的问题。要充分利用这些算法，对它们的逻辑和数学有更深入的理解是必不可少的。您将从算法介绍开始，探索各种算法设计技术。接着，您将了解线性规划、页面排名和图表，甚至使用机器学习算法，理解它们背后的数学和逻辑。本书还包含案例研究，如天气预测、推文聚类和电影推荐引擎，将向您展示如何最优地应用这些算法。完成本书后，您将自信地使用算法解决现实世界的计算问题。

本书适合对象

本书适合严肃的程序员！无论您是经验丰富的程序员，希望更深入地了解算法背后的数学，还是对编程或数据科学知识有限，想了解如何利用经过实战检验的算法来改进设计和编写代码的方式，您都会发现本书很有用。必须具备 Python 编程经验，尽管了解数据科学有所帮助，但并非必需。

本书涵盖内容

第一章《算法概述》总结了算法的基本原理。它从需要理解不同算法工作原理的基本概念开始。它总结了人们如何开始使用算法来数学地表达某些类别的问题。它还提到了不同算法的局限性。接下来的部分解释了指定算法逻辑的各种方法。由于本书使用 Python 编写算法，因此接下来解释了如何设置环境以运行示例。然后，讨论了衡量算法性能并与其他算法进行比较的各种方法。最后，本章讨论了验证算法特定实现的各种方法。

第二章《算法中使用的数据结构》着重于算法对必要的内存数据结构的需求，这些数据结构可以保存临时数据。算法可以是数据密集型、计算密集型或两者兼而有之。但对于所有不同类型的算法，选择正确的数据结构对于它们的最佳实现至关重要。许多算法具有递归和迭代逻辑，并且需要基本上是迭代性质的专门数据结构。由于本书使用 Python，本章重点介绍了可以用于实现本书讨论的算法的 Python 数据结构。

第三章《排序和搜索算法》介绍了用于排序和搜索的核心算法。这些算法以后可以成为更复杂算法的基础。本章首先介绍了不同类型的排序算法。它还比较了各种方法的性能。然后，介绍了各种搜索算法。它们进行了比较，并量化了它们的性能和复杂性。最后，本章介绍了这些算法的实际应用。

第四章《设计算法》介绍了各种算法的核心设计概念。它还解释了不同类型的算法，并讨论了它们的优缺点。在设计复杂算法时，理解这些概念是很重要的。该章首先讨论了不同类型的算法设计。然后，它提出了著名的旅行推销员问题的解决方案。接着讨论了线性规划及其局限性。最后，它提出了一个实际例子，展示了线性规划如何用于容量规划。

第五章《图算法》专注于计算机科学中常见的图问题的算法。有许多计算问题最好以图的术语表示。本章介绍了表示图和搜索图的方法。搜索图意味着系统地沿着图的边缘访问图的顶点。图搜索算法可以发现关于图结构的许多信息。许多算法首先通过搜索它们的输入图来获得这些结构信息。几种其他图算法详细介绍了基本的图搜索。搜索图的技术是图算法领域的核心。第一部分讨论了图的两种最常见的计算表示形式：邻接表和邻接矩阵。接下来介绍了一种简单的图搜索算法，称为广度优先搜索，并展示了如何创建广度优先树。接着介绍了深度优先搜索，并提供了一些关于深度优先搜索访问顶点顺序的标准结果。

第六章《无监督机器学习算法》介绍了无监督机器学习算法。这些算法被分类为无监督，因为模型或算法试图从给定数据中学习内在结构、模式和关系，而无需任何监督。首先讨论了聚类方法。这些是机器学习方法，试图在数据样本中找到相似性和关系的模式，然后将这些样本聚类成各种群组，使得每个数据样本的群组或簇都具有一定的相似性，基于内在属性或特征。接下来讨论了降维算法，当我们最终拥有大量特征时使用。接着介绍了一些处理异常检测的算法。最后，本章介绍了关联规则挖掘，这是一种数据挖掘方法，用于检查和分析大型交易数据集，以识别感兴趣的模式和规则。这些模式代表跨交易的各种项目之间的有趣关系和关联。

第七章《传统监督学习算法》描述了传统的监督机器学习算法，涉及一组机器学习问题，其中存在带有输入属性和相应输出标签或类别的标记数据集。然后利用这些输入和相应的输出来学习一个泛化系统，可以用来预测以前未见过的数据点的结果。首先，在机器学习的背景下介绍了分类的概念。然后介绍了最简单的机器学习算法之一，线性回归。接着介绍了最重要的算法之一，决策树。讨论了决策树算法的局限性和优势，然后介绍了两个重要的算法，SVM 和 XGBoost。

第八章《神经网络算法》首先介绍了典型神经网络的主要概念和组件，这种网络正成为最重要的机器学习技术。然后，它介绍了各种类型的神经网络，并解释了用于实现这些神经网络的各种激活函数。接着详细讨论了反向传播算法，这是最广泛使用的收敛神经网络问题的算法。接下来解释了迁移学习技术，可以大大简化和部分自动化模型的训练。最后，介绍了如何使用深度学习来检测多媒体数据中的对象作为实际例子。

第九章《自然语言处理算法》介绍了自然语言处理（NLP）的算法。本章以渐进的方式从理论到实践。首先介绍了基本原理，然后是基础数学知识。然后讨论了设计和实施几个重要的文本数据用例的最广泛使用的神经网络之一。还讨论了 NLP 的局限性。最后，介绍了一个案例研究，其中训练模型以根据写作风格检测论文的作者。

第十章《推荐引擎》专注于推荐引擎，这是一种对用户偏好相关信息进行建模，并利用这些信息提供有根据的推荐的方法。推荐引擎的基础始终是用户和产品之间记录的互动。本章首先介绍了推荐引擎背后的基本思想。然后讨论了各种类型的推荐引擎。最后，讨论了推荐引擎如何用于向不同用户推荐物品和产品。

第十一章《数据算法》关注与数据中心算法相关的问题。该章从简要概述与数据相关的问题开始。然后介绍了对数据进行分类的标准。接下来提供了如何将算法应用于流数据应用程序的描述，然后介绍了密码学的主题。最后，介绍了从 Twitter 数据中提取模式的实际例子。

第十二章《密码学》介绍了与密码学相关的算法。该章从背景开始。然后讨论了对称加密算法。解释了 MD5 和 SHA 哈希算法，并介绍了实施对称算法的局限性和弱点。接下来讨论了非对称加密算法以及它们如何用于创建数字证书。最后，讨论了一个总结所有这些技术的实际例子。

第十三章《大规模算法》解释了如何处理无法适应单个节点内存并涉及需要多个 CPU 进行处理的数据的大规模算法。本章首先讨论了最适合并行运行的算法类型。然后讨论了与并行化算法相关的问题。还介绍了 CUDA 架构，并讨论了如何使用单个 GPU 或一组 GPU 来加速算法以及需要对算法进行哪些更改才能有效利用 GPU 的性能。最后，本章讨论了集群计算，并讨论了 Apache Spark 如何创建弹性分布式数据集（RDD）以创建标准算法的极快并行实现。

第十四章，实际考虑，从解释性的重要主题开始，这在现在已经解释了自动决策背后的逻辑变得越来越重要。然后，本章介绍了使用算法的伦理和在实施它们时可能产生偏见的可能性。接下来，详细讨论了处理 NP-hard 问题的技术。最后，总结了实施算法的方法以及与此相关的现实挑战。

充分利用本书

如果您使用本书的数字版本，我们建议您自己输入代码或通过 GitHub 存储库（链接在下一节中提供）访问代码。这样做将有助于避免与复制和粘贴代码相关的任何潜在错误。

下载示例代码文件

您可以从您的账户在www.packt.com下载本书的示例代码文件。如果您在其他地方购买了本书，您可以访问www.packtpub.com/support并注册，文件将直接发送到您的邮箱。

您可以按照以下步骤下载代码文件：

1. 在www.packt.com登录或注册。
   
2. 选择“支持”选项卡。
   
3. 点击“代码下载”。
   
4. 在搜索框中输入书名，然后按照屏幕上的说明进行操作。
   

文件下载后，请确保使用最新版本进行解压缩或提取文件夹：

• Windows 的 WinRAR/7-Zip
  
• Mac 的 Zipeg/iZip/UnRarX
  
• Linux 的 7-Zip/PeaZip
  

该书的代码包也托管在 GitHub 上，网址为github.com/PacktPublishing/40-Algorithms-Every-Programmer-Should-Know。如果代码有更新，将在现有的 GitHub 存储库上进行更新。

我们还有来自我们丰富书籍和视频目录的其他代码包，可在**github.com/PacktPublishing/**上找到。去看看吧！

下载彩色图片

我们还提供了一个 PDF 文件，其中包含本书中使用的屏幕截图/图表的彩色图片。您可以在这里下载：static.packt-cdn.com/downloads/9781789801217_ColorImages.pdf。

使用的约定

本书中使用了许多文本约定。

CodeInText：表示文本中的代码单词，数据库表名，文件夹名，文件名，文件扩展名，路径名，虚拟 URL，用户输入和 Twitter 句柄。这里有一个例子：“让我们看看如何通过使用push来向堆栈添加一个新元素，或者通过使用pop来从堆栈中移除一个元素。”

代码块设置如下：

define swap(x, y)
    buffer = x
    x = y
    y = buffer

当我们希望引起您对代码块的特定部分的注意时，相关行或项目将以粗体显示：

define swap(x, y)
    buffer = x
    x = y
 y = buffer

任何命令行输入或输出都以以下方式编写：

pip install a_package

粗体：表示一个新术语，一个重要单词，或者屏幕上看到的单词。例如，菜单或对话框中的单词会以这种方式出现在文本中。这里有一个例子：“简化算法的一种方法是在准确性上做出妥协，从而产生一种称为近似算法的算法。”

警告或重要提示会以这种方式出现。提示和技巧会以这种方式出现。

第一部分：基本原理和核心算法

本节介绍了算法的核心方面。我们将探讨算法是什么以及如何设计它，还将了解算法中使用的数据结构。本节还深入介绍了排序和搜索算法，以及解决图形问题的算法。本节包括以下章节：

• 第一章，算法概述
  
• 第二章，算法中使用的数据结构
  
• 第三章，排序和搜索算法
  
• 第四章，设计算法
  
• 第五章，图算法
  

第一章：算法概述

本书涵盖了理解、分类、选择和实施重要算法所需的信息。除了解释它们的逻辑之外，本书还讨论了适用于不同类算法的数据结构、开发环境和生产环境。我们专注于越来越重要的现代机器学习算法。除了逻辑之外，还提供了算法实际解决日常问题的实际示例。

本章介绍了算法基础知识。它从需要理解不同算法工作原理的基本概念开始。本节总结了人们如何开始使用算法来数学表达某一类问题，并提到了不同算法的局限性。接下来的部分解释了指定算法逻辑的各种方法。由于本书使用 Python 编写算法，因此解释了如何设置环境来运行示例。然后，讨论了算法性能可以如何量化并与其他算法进行比较的各种方法。最后，本章讨论了验证算法特定实现的各种方法。

总之，本章涵盖了以下主要内容：

• 什么是算法？
  
• 指定算法的逻辑
  
• 介绍 Python 包
  
• 算法设计技术
  
• 性能分析
  
• 验证算法
  

什么是算法？

简单来说，算法是一组用于解决问题的计算规则。它旨在根据精确定义的指令为任何有效输入产生结果。如果您在英语词典（如美国传统）中查找算法一词，它定义了以下概念：

“算法是一组明确的指令，给定一些初始条件，可以按照规定的顺序执行，以达到某个目标，并具有可识别的一组结束条件。”

设计算法是创建数学配方的努力，以最有效的方式解决现实世界的问题。这个配方可以作为开发更可重用和通用的数学解决方案的基础，可以应用于更广泛的类似问题集。

算法的阶段

以下图表说明了开发、部署和最终使用算法的不同阶段：

正如我们所看到的，这个过程始于理解问题陈述中的需求，详细说明了需要做什么。一旦问题清晰陈述，就会引导我们进入开发阶段。

开发阶段包括两个阶段：

• 设计阶段：在设计阶段，算法的架构、逻辑和实现细节被构想和记录下来。在设计算法时，我们同时考虑准确性和性能。在寻找给定问题的解决方案时，在许多情况下，我们会得到多个备选算法。算法的设计阶段是一个迭代过程，涉及比较不同的候选算法。一些算法可能提供简单快速的解决方案，但可能会牺牲准确性。其他算法可能非常准确，但由于复杂性需要花费相当长的时间来运行。其中一些复杂算法可能比其他算法更有效。在做出选择之前，应仔细研究候选算法的所有固有权衡。特别是对于复杂问题，设计高效的算法非常重要。正确设计的算法将导致有效的解决方案，能够同时提供令人满意的性能和合理的准确性。
  
• 编码阶段：在编码阶段，设计的算法被转换为计算机程序。实际程序实现设计阶段建议的所有逻辑和架构是很重要的。
  

算法的设计和编码阶段是迭代的。设计满足功能和非功能需求的设计可能需要大量的时间和精力。功能需求是指定给定输入数据的正确输出是什么的要求。算法的非功能需求主要是关于给定数据大小的性能。算法的验证和性能分析将在本章后面讨论。验证算法是验证算法是否满足其功能需求。算法的性能分析是验证它是否满足其主要的非功能需求：性能。

一旦设计并在您选择的编程语言中实现，算法的代码就可以部署了。部署算法涉及设计实际的生产环境，代码将在其中运行。生产环境需要根据算法的数据和处理需求进行设计。例如，对于可并行化的算法，需要具有适当数量的计算节点的集群，以便有效地执行算法。对于数据密集型算法，可能需要设计数据进入管道和缓存和存储数据的策略。生产环境的设计将在第十三章“大规模算法”和第十四章“实际考虑”中更详细地讨论。一旦设计并实施了生产环境，算法就可以部署，它将接受输入数据，处理它，并根据要求生成输出。

指定算法的逻辑

在设计算法时，重要的是找到不同的方式来指定其细节。需要能够捕捉其逻辑和架构。通常，就像建造房屋一样，在实际实施算法之前，指定算法的结构是很重要的。对于更复杂的分布式算法，预先规划它们的逻辑在运行时如何分布在集群中对于迭代式高效设计过程是重要的。通过伪代码和执行计划，这两个需求都得到满足，并将在下一节中讨论。

理解伪代码

指定算法逻辑的最简单方法是以半结构化方式编写算法的高级描述，称为伪代码。在用伪代码编写逻辑之前，首先描述其主要流程并用简单的英语写出主要步骤是有帮助的。然后，将这个英语描述转换成伪代码，这是一种以结构化方式编写这个英语描述的方法，它紧密地代表了算法的逻辑和流程。良好编写的算法伪代码应该以合理的细节描述算法的高级步骤，即使详细的代码与主要流程和结构无关。下图显示了步骤的流程：

伪代码的一个实际例子

请注意，一旦编写了伪代码（如我们将在下一节中看到的），我们就可以使用我们选择的编程语言编写算法代码了。

图 1.3 显示了一个名为SRPMP的资源分配算法的伪代码。在集群计算中，有许多情况需要在一组可用资源上运行并行任务，统称为资源池。这个算法将任务分配给一个资源，并创建一个称为Ω的映射集。请注意，所呈现的伪代码捕捉了算法的逻辑和流程，这在下一节中进一步解释：

1: BEGIN Mapping_Phase
2: Ω = { }
3: k = 1
4: FOREACH Ti∈T
5:     ωi = RA(Δk,Ti)
6:     add {ωi,Ti} to Ω
7:     state_changeTi [STATE 0: Idle/Unmapped] → [STATE 1: Idle/Mapped]
8:     k=k+1
9:     IF (k>q)
10:       k=1
11:    ENDIF
12: END FOREACH
13: END Mapping_Phase

让我们逐行解析这个算法：

1. 我们通过执行算法开始映射。Ω映射集是空的。
   
2. 第一个分区被选为T[1]任务的资源池（参见前面代码的第 3 行）。电视收视率（TRPS）迭代地调用类风湿性关节炎（RA）算法，对于每个T[i]任务，选择一个分区作为资源池。
   
3. RA 算法返回为T[i]任务选择的资源集，由ω[i]表示（参见前面代码的第 5 行）。
   
4. T[i]和ω[i]被添加到映射集中（参见前面代码的第 6 行）。
   
5. T[i]的状态从STATE 0:Idle/Mapping更改为STATE 1:Idle/Mapped（参见前面代码的第 7 行）。
   
6. 请注意，对于第一次迭代，k=1，并且选择了第一个分区。对于每个后续迭代，k的值增加，直到k>q。
   
7. 如果k变得大于q，它会再次重置为1（参见前面代码的第 9 和第 10 行）。
   
8. 这个过程重复进行，直到确定并存储了所有任务与它们将使用的资源集之间的映射，并存储在一个称为Ω的映射集中。
   
9. 一旦每个任务在映射阶段映射到一组资源中，它就会被执行。
   

使用片段

随着 Python 等简单但功能强大的编程语言的流行，另一种替代方法变得流行，即直接用编程语言表示算法的逻辑，以一种简化的方式。与伪代码一样，这个选定的代码捕捉了所提出的算法的重要逻辑和结构，避免了详细的代码。这个选定的代码有时被称为片段。在本书中，尽可能使用片段代替伪代码，因为它们节省了一个额外的步骤。例如，让我们看一个简单的片段，它是一个关于可以用来交换两个变量的 Python 函数的片段：

define swap(x, y)
    buffer = x
    x = y
    y = buffer

请注意，片段并不能总是替代伪代码。在伪代码中，有时我们将许多行代码抽象为一行伪代码，表达算法的逻辑，而不会被不必要的编码细节分散注意力。

创建执行计划

伪代码和片段并不总是足以指定与更复杂的分布式算法相关的所有逻辑。例如，分布式算法通常需要在运行时分成不同的编码阶段，这些阶段具有优先顺序。将较大的问题划分为最佳数量的阶段，并具有正确的优先约束条件的正确策略对于有效执行算法至关重要。

我们需要找到一种方法来表示这种策略，以完全表示算法的逻辑和结构。执行计划是详细说明算法将如何被细分为一堆任务的一种方式。一个任务可以是映射器或减速器，可以被分组在称为阶段的块中。下图显示了在执行算法之前由 Apache Spark 运行时生成的执行计划。它详细说明了作业为执行我们的算法创建的运行时任务将被分成：

请注意，前面的图表有五个任务，它们被分成了两个不同的阶段：阶段 11 和阶段 12。

引入 Python 包

一旦设计好算法，就需要根据设计在编程语言中实现。对于本书，我选择了编程语言 Python。我选择它是因为 Python 是一种灵活的开源编程语言。Python 也是越来越重要的云计算基础设施的首选语言，如亚马逊网络服务（AWS）、微软 Azure 和谷歌云平台（GCP）。

官方 Python 主页可在www.python.org/找到，其中还有安装说明和有用的初学者指南。

如果您以前没有使用过 Python，浏览这本初学者指南是一个好主意。对 Python 的基本理解将有助于您更好地理解本书中提出的概念。

对于本书，我希望您使用最新版本的 Python 3。在撰写本文时，最新版本是 3.7.3，这是我们将用来运行本书中的练习的版本。

Python 软件包

Python 是一种通用语言。它设计成具有最基本的功能。根据您打算使用 Python 的用例，需要安装额外的软件包。安装额外软件包的最简单方法是通过 pip 安装程序。这个pip命令可以用来安装额外的软件包：

pip install a_package

已安装的软件包需要定期更新以获得最新功能。这可以通过使用upgrade标志来实现：

pip install a_package --upgrade

用于科学计算的另一个 Python 发行版是 Anaconda，可以从continuum.io/downloads下载。

除了使用pip命令安装新软件包外，对于 Anaconda 发行版，我们还可以使用以下命令来安装新软件包：

conda install a_package

要更新现有的软件包，Anaconda 发行版提供了以下命令选项：

conda update a_package

有各种各样的 Python 软件包可用。一些与算法相关的重要软件包在以下部分中进行了描述。

SciPy 生态系统

科学 Python（SciPy）——发音为sigh pie——是为科学界创建的一组 Python 软件包。它包含许多函数，包括各种随机数生成器、线性代数例程和优化器。SciPy 是一个综合性的软件包，随着时间的推移，人们开发了许多扩展来根据自己的需求定制和扩展软件包。

以下是该生态系统的主要软件包：

• NumPy：对于算法来说，创建多维数据结构（如数组和矩阵）的能力非常重要。NumPy 提供了一组重要的用于统计和数据分析的数组和矩阵数据类型。有关 NumPy 的详细信息可以在www.numpy.org/找到。
  
• scikit-learn：这个机器学习扩展是 SciPy 最受欢迎的扩展之一。Scikit-learn 提供了一系列重要的机器学习算法，包括分类、回归、聚类和模型验证。您可以在scikit-learn.org/找到有关 scikit-learn 的更多详细信息。
  
• pandas：pandas 是一个开源软件库。它包含了广泛用于输入、输出和处理表格数据的表格复杂数据结构。pandas 库包含许多有用的函数，还提供了高度优化的性能。有关 pandas 的更多详细信息可以在pandas.pydata.org/找到。
  
• Matplotlib：Matplotlib 提供了创建强大可视化的工具。数据可以呈现为折线图、散点图、条形图、直方图、饼图等。更多信息可以在matplotlib.org/找到。
  
• Seaborn：Seaborn 可以被认为类似于 R 中流行的 ggplot2 库。它基于 Matplotlib，并提供了一个高级接口来绘制出色的统计图形。更多细节可以在seaborn.pydata.org/找到。
  
• iPython：iPython 是一个增强的交互式控制台，旨在促进编写，测试和调试 Python 代码。
  
• 运行 Python 程序：交互式编程模式对于学习和实验代码非常有用。 Python 程序可以保存在带有.py扩展名的文本文件中，并且可以从控制台运行该文件。
  

通过 Jupyter Notebook 实现 Python

通过 Jupyter Notebook 运行 Python 程序的另一种方式。 Jupyter Notebook 提供了基于浏览器的用户界面来开发代码。 Jupyter Notebook 用于在本书中展示代码示例。 用文本和图形注释和描述代码的能力使其成为呈现和解释算法的完美工具，也是学习的好工具。

要启动笔记本，您需要启动Juypter-notebook进程，然后打开您喜欢的浏览器并导航到http://localhost:8888：

请注意，Jupyter Notebook 由称为单元格的不同块组成。

算法设计技术

算法是对现实世界问题的数学解决方案。在设计算法时，我们在设计和微调算法时牢记以下三个设计关注点：

• 关注 1：这个算法是否产生了我们预期的结果？
  
• 关注 2：这是获得这些结果的最佳方式吗？
  
• 关注 3：算法在更大的数据集上的表现如何？
  

在设计解决方案之前更好地了解问题本身的复杂性是很重要的。例如，如果我们根据需求和复杂性对问题进行表征，这有助于我们设计适当的解决方案。通常，根据问题的特征，算法可以分为以下类型：

• 数据密集型算法：数据密集型算法旨在处理大量数据。预计它们具有相对简单的处理要求。应用于大型文件的压缩算法是数据密集型算法的一个很好的例子。对于这样的算法，数据的大小预计会远大于处理引擎（单个节点或集群）的内存，并且可能需要开发迭代处理设计以根据要求高效处理数据。
  
• 计算密集型算法：计算密集型算法具有相当大的处理需求，但不涉及大量数据。一个简单的例子是查找非常大的质数的算法。找到将算法分成不同阶段的策略，以便至少有一些阶段是并行化的，是最大化算法性能的关键。
  
• 数据和计算密集型算法：有些算法处理大量数据，并且具有相当大的计算需求。用于对实时视频流执行情感分析的算法是处理任务中数据和处理要求都很大的很好的例子。这些算法是最资源密集的算法，需要仔细设计算法并智能分配可用资源。
  

为了更深入地研究问题的复杂性和需求，有助于我们研究其数据并计算更深入的维度，这将在下一节中进行。

数据维度

为了对问题的数据维度进行分类，我们看看其体积，速度和多样性（3V），其定义如下：

• 体积：体积是算法将处理的数据的预期大小。
  
• 速度：速度是在使用算法时预期的新数据生成速率。它可以为零。
  
• 多样性：多样性量化了设计的算法预计要处理多少不同类型的数据。
  

下图更详细地显示了数据的 3Vs。这个图的中心显示了最简单的数据，体积小，多样性和速度低。当我们远离中心时，数据的复杂性增加。它可以在三个维度中的一个或多个维度上增加。例如，在速度维度上，我们有批处理作为最简单的，然后是周期性处理，然后是准实时处理。最后，我们有实时处理，在数据速度的背景下处理起来最复杂。例如，由一组监控摄像头收集的实时视频流将具有高体积、高速度和高多样性，并且可能需要适当的设计来有效地存储和处理数据。另一方面，一个在 Excel 中创建的简单.csv文件将具有低体积、低速度和低多样性：

例如，如果输入数据是一个简单的csv文件，那么数据的体积、速度和多样性将很低。另一方面，如果输入数据是安全视频摄像头的实时视频流，那么数据的体积、速度和多样性将会很高，这个问题在设计算法时应该牢记在心。

计算维度

计算维度是关于问题处理和计算需求的。算法的处理需求将决定最有效的设计是什么样的。例如，深度学习算法通常需要大量的处理能力。这意味着对于深度学习算法，尽可能拥有多节点并行架构是很重要的。

一个实际的例子

假设我们想对一个视频进行情感分析。情感分析是指我们试图标记视频中不同部分的人类情感，如悲伤、快乐、恐惧、喜悦、挫折和狂喜。这是一个计算密集型的工作，需要大量的计算能力。正如你将在下图中看到的，为了设计计算维度，我们将处理分为五个任务，包括两个阶段。所有的数据转换和准备都是在三个 mapper 中实现的。为此，我们将视频分成三个不同的分区，称为拆分。在 mapper 执行完毕后，处理后的视频输入到两个聚合器，称为reducer。为了进行所需的情感分析，reducer 根据情感对视频进行分组。最后，结果在输出中合并。

请注意，mapper 的数量直接影响算法的运行并行性。最佳的 mapper 和 reducer 数量取决于数据的特性、需要使用的算法类型以及可用资源的数量。

性能分析

分析算法的性能是设计的重要部分。估计算法性能的一种方法是分析其复杂性。

复杂性理论是研究复杂算法的学科。为了有用，任何算法都应该具有三个关键特征：

• 应该是正确的。如果算法不能给出正确的答案，那么它对你来说没有太大的好处。
  
• 一个好的算法应该是可以理解的。即使是世界上最好的算法，如果对你来说太复杂而无法在计算机上实现，那也没有什么好处。
  
• 一个好的算法应该是高效的。即使一个算法产生了正确的结果，如果它需要花费一千年或者需要十亿太字节的内存，也不会对你有太大帮助。
  

算法复杂度的两种可能的分析类型：

• 空间复杂度分析：估计执行算法所需的运行时内存需求。
  
• 时间复杂度分析：估计算法运行所需的时间。
  

空间复杂度分析

空间复杂度分析估计算法处理输入数据所需的内存量。在处理输入数据时，算法需要将瞬态临时数据结构存储在内存中。算法的设计方式会影响这些数据结构的数量、类型和大小。在分布式计算时代，需要处理越来越多的数据，空间复杂度分析变得越来越重要。这些数据结构的大小、类型和数量将决定底层硬件的内存需求。在分布式计算中使用的现代内存数据结构，如弹性分布式数据集（RDD），需要具有高效的资源分配机制，以便在算法的不同执行阶段了解内存需求。

空间复杂度分析是算法高效设计的必要条件。如果在设计特定算法时没有进行适当的空间复杂度分析，那么对于瞬态临时数据结构的内存可用性不足可能会触发不必要的磁盘溢出，这可能会显著影响算法的性能和效率。

在本章中，我们将更深入地研究时间复杂度。空间复杂度将在第十三章《大规模算法》中更详细地讨论，那里我们将处理具有复杂运行时内存需求的大规模分布式算法。

时间复杂度分析

时间复杂度分析估计算法基于其结构完成其分配工作所需的时间。与空间复杂度相比，时间复杂度不依赖于算法将在其上运行的任何硬件。时间复杂度分析仅仅取决于算法本身的结构。时间复杂度分析的总体目标是尝试回答这些重要问题——这个算法是否可扩展？这个算法将如何处理更大的数据集？

为了回答这些问题，我们需要确定算法在数据规模增大时对性能的影响，并确保算法不仅准确而且能够良好扩展。在当今“大数据”世界中，算法的性能对于更大的数据集变得越来越重要。

在许多情况下，我们可能有多种方法来设计算法。在这种情况下进行时间复杂度分析的目标将是：

“对于一个特定的问题和多个算法，哪一个在时间效率上最有效？”

计算算法时间复杂度的基本方法有两种：

• 后实现的分析方法：在这种方法中，实现不同的候选算法并比较它们的性能。
  
• 预实现的理论方法：在运行算法之前，通过数学近似来估计每个算法的性能。
  

理论方法的优势在于它仅仅取决于算法本身的结构。它不依赖于实际用于运行算法的硬件、运行时选择的软件栈的选择，或者用于实现算法的编程语言。

性能估计

典型算法的性能将取决于输入的数据类型。例如，如果数据已根据我们试图解决的问题的上下文进行了排序，算法可能会执行得非常快。如果排序后的输入用于基准测试这个特定的算法，那么它将给出一个不真实的良好性能数字，这不会真实反映其在大多数情况下的真实性能。为了处理算法对输入数据的依赖性，我们在进行性能分析时需要考虑不同类型的情况。

最佳情况

在最佳情况下，输入的数据组织方式使得算法能够发挥最佳性能。最佳情况分析给出了算法性能的上限。

最坏情况

估计算法性能的第二种方法是尝试找到在给定一组条件下完成工作所需的最长时间。算法的最坏情况分析非常有用，因为我们保证无论条件如何，算法的性能始终优于我们分析出来的数字。最坏情况分析在处理具有更大数据集的复杂问题时特别有用。最坏情况分析给出了算法性能的下限。

平均情况

这从将各种可能的输入分成各种组开始。然后，从每个组的一个代表性输入进行性能分析。最后，计算每个组的性能的平均值。

平均情况分析并不总是准确的，因为它需要考虑算法的所有不同组合和可能性，这并不总是容易做到。

选择算法

你怎么知道哪一个是更好的解决方案？你怎么知道哪个算法运行得更快？时间复杂度和大 O 符号（本章后面讨论）是回答这些问题的非常好的工具。

要看它在哪里有用，让我们举一个简单的例子，目标是对一组数字进行排序。有几种可用的算法可以完成这项工作。问题是如何选择正确的算法。

首先，可以观察到的一点是，如果列表中的数字不太多，那么我们选择哪种算法来对数字列表进行排序就无关紧要。因此，如果列表中只有 10 个数字（n=10），那么我们选择哪种算法都无关紧要，因为即使是设计非常糟糕的算法，也可能不会花费超过几微秒的时间。但是一旦列表的大小变成 100 万，现在选择正确的算法将会有所不同。一个非常糟糕的算法甚至可能需要几个小时才能运行，而一个设计良好的算法可能在几秒内完成对列表的排序。因此，对于更大的输入数据集，投入时间和精力进行性能分析，并选择正确设计的算法来高效地完成所需的工作是非常有意义的。

大 O 符号

大 O 符号用于量化各种算法的性能，随着输入规模的增长。大 O 符号是进行最坏情况分析的最流行方法之一。本节讨论了不同类型的大 O 符号。

常数时间（O(1)）复杂度

如果一个算法在运行时所需的时间与输入数据的大小无关，那么它被称为以常数时间运行。它用 O(1)表示。让我们以访问数组的第 n 个元素为例。无论数组的大小如何，获取结果都需要恒定的时间。例如，以下函数将返回数组的第一个元素，并具有 O(1)的复杂度：

def getFirst(myList):
    return myList[0]

输出如下：

• 通过使用push添加新元素到栈或使用pop从栈中移除元素。无论栈的大小如何，添加或移除元素都需要相同的时间。
  
• 访问哈希表的元素（如第二章中讨论的，算法中使用的数据结构）。
  
• 桶排序（如第二章中讨论的，算法中使用的数据结构）。
  

线性时间（O(n)）复杂度

如果执行时间与输入大小成正比，则称算法具有线性时间复杂度，表示为 O(n)。一个简单的例子是在单维数据结构中添加元素：

def getSum(myList):
    sum = 0
    for item in myList:
        sum = sum + item
    return sum

请注意算法的主循环。主循环中的迭代次数随着n的增加而线性增加，产生了下图中的 O(n)复杂度：

数组操作的其他一些例子如下：

• 搜索一个元素
  
• 在数组的所有元素中找到最小值
  

二次时间（O(n²)）复杂度

如果算法的执行时间与输入大小的平方成正比，则称算法具有二次时间复杂度；例如，一个简单的函数对二维数组求和如下：

def getSum(myList):
    sum = 0
    for row in myList:
        for item in row:
            sum += item
    return sum

请注意主循环内嵌在另一个主循环中。这个嵌套循环使得前面的代码具有 O(n²)的复杂度：

另一个例子是冒泡排序算法（如第二章中讨论的，算法中使用的数据结构）。

对数时间（O(logn)）复杂度

如果算法的执行时间与输入大小的对数成正比，则称算法具有对数时间复杂度。每次迭代，输入大小都会以一个常数倍数因子减少。对数的一个例子是二分搜索。二分搜索算法用于在一维数据结构中查找特定元素，例如 Python 列表。数据结构中的元素需要按降序排序。二分搜索算法在名为searchBinary的函数中实现，如下所示：

def searchBinary(myList,item):
    first = 0
    last = len(myList)-1
    foundFlag = False
    while( first<=last and not foundFlag):
        mid = (first + last)//2
        if myList[mid] == item :
            foundFlag = True
        else:
            if item < myList[mid]:
                last = mid - 1
            else:
                first = mid + 1
    return foundFlag

主循环利用列表有序的事实。它每次迭代将列表分成一半，直到得到结果：

在定义函数之后，测试了在第 11 和 12 行搜索特定元素。二分搜索算法在第三章中进一步讨论，排序和搜索算法。

请注意，在所提出的四种大 O 符号类型中，O(n²)的性能最差，O(logn)的性能最佳。事实上，O(logn)的性能可以被视为任何算法性能的黄金标准（尽管并非总是实现）。另一方面，O(n²)并不像 O(n³)那么糟糕，但是仍然，属于这一类的算法不能用于大数据，因为时间复杂度对它们能够实际处理的数据量施加了限制。

减少算法复杂度的一种方法是在准确性上做出妥协，产生一种称为近似算法的算法类型。

算法性能评估的整个过程是迭代的，如下图所示：

每个程序员都应该知道的 40 个算法（一）（2）https://developer.aliyun.com/article/1506325