在数据科学中，计算机科学和统计学融合在一起。作为数据科学家，我们使用统计原理来编写代码，以便能够有效地探索手头的问题。

这需要至少对数据结构，算法和时间空间复杂度的基本理解这样我们就能更有效地编程并理解我们使用的工具。对于更大的数据集，这就变得尤为重要。我们编写代码的方式会影响数据分析的速度，从而得出相应的结论。在这篇文章中，我将描述大O符号作为一种描述时空复杂度的方法，并简要介绍一些与时间复杂度相关的算法。在以后的文章中，我将讨论与空间复杂性相关的算法。

大O符号

在编程中，算法是为了达到特定目标而要遵循的过程或规则集。一个算法的特点是它的运行时间(运行时)，无论是在空间上还是在时间上。作为数据科学家，我们对最高效的算法感兴趣，这样我们就可以优化我们的工作流程。

在计算机科学中，大O符号是通过比较算法内的操作数来描述算法的“快速”增长。稍后会详细解释，但现在，让我们来理解所有的形式符号。

正式的符号

• 大Ω:最好的情况。大Ω的算法描述了如何快速算法可以在最好的情况下运行。
• 大O:最坏的情况。通常，我们最关心的是大O时间，因为我们最关心的是给定算法的运行速度。我们如何使最坏情况不像它可能的那么糟呢?
• 大θ:这只能被用来描述一个算法的运行时如果大Ω,大魔神都是相同的。也就是说，算法的运行时间在最好和最坏的情况下都是相同的。

因为我们最关心的是算法的大O，所以本文的其余部分将只关注大O。

我们如何用大O来描述一个算法?假设你想在电话簿里搜索某人的名字。

找到这个人最直接的方法是什么？你可以查看电话簿中的每个名字，直到找到你的目标。这被称为简单搜索。

如果电话簿非常小，只有10个名字，这是一个相当快的过程。但如果电话簿中有1000个名字怎么办？

您的目标名称位于列表的前面，您只需要检查第一项。在最坏的情况下，您的目标名称位于电话簿的最末端，您需要搜索所有1000个名称。随着“数据集”（或电话簿）的大小增加，运行简单搜索所需的最长时间也会线性增加。

在这种情况下，我们的算法是一个简单的搜索。Big O表示法允许我们描述最糟糕的情况。在这种情况下，我们最糟糕的情况是我们将不得不搜索电话簿中的所有元素（n）。我们可以将运行时描述为：

O(n) where n: number of operations

因为最大操作次数等于我们电话簿中的最大元素数（您可能需要搜索它们以查找目标的名称），我们说简单搜索的Big O是O（n）。简单的搜索永远不会比O（n）时间慢。

不同的大O运行时间

不同的算法有不同的运行时间。也就是说，算法以不同的速度增长。最常见的大O运行时间，从最快到最慢，是:

• O(log n):也就是log time
• O(n):又称线性时间
• O(n log n)
• O(n²)
• O(n !)

对于不同运行时间的快速图形表示以及它们之间的比较，大O cheatsheet也非常有用。

常见Big O运行时间的图形表示

下面是一些在讨论一些常见算法之前需要了解的重要原则。

递归:递归是指函数调用自身。也许递归的典型例子是实现阶乘函数:

def factorial(n):

if n < 1: #base case

return 1

else: #recursive case

return n * factorial(n-1)

Divide and Conquer(D&C):一种解决问题的递归方法，D&C(1)确定问题的最简单情况(又名基本情况,the base case)，(2)减少问题，直到现在成为基本情况。

也就是说，一个复杂的问题被分解成更简单的子问题。这些子问题得到了解决，然后将它们的解决方案组合起来，以解决原来更大的问题。

常见的算法

搜索和排序算法可能是首先要了解的最重要的算法。

搜索

• 简单搜索

这在前面的电话簿示例中进行了描述，最糟糕的情况是要求您在找到感兴趣的名称之前搜索电话簿中的所有名称。通常，简单搜索具有O（n）时间。所需的最长时间与列表中的元素数量线性相关。

• 二分搜索

让我们坚持使用电话簿示例。我们仍然有兴趣在电话簿中找到某人的名字，但这次我们将尝试提高效率。我们不是单调乏味地浏览电话簿中的每个名字，而是从电话簿的中间开始，然后从那里开始。

假设我们的目标名称以P开头。我们打开大致位于字母表中间的M s。我们知道M比字母表中的P早，所以我们可以消除从A到M的部分。现在我们可以看一下电话簿的后半部分（N到Z），将该部分分成中间（到Ts）），并与我们的目标进行比较。T在字母表中比P稍晚。然后我们知道消除后半部分（T到Z）。我们专注于N到S.现在，把它分成两半，依此类推，直到找到我们感兴趣的名字。

通常，在二分搜索中，您可以获取已排序（这很重要）的数据并找到中点。每次，您将目标与中间值进行比较。如果目标值与中间值相同，那么您的工作就完成了。否则，您知道根据比较消除列表的哪一半。您继续分割，直到找到目标或数据集不能再减半。

二分搜索图与数字列表

由于二分搜索涉及数据集减半，因此Big O时间为O（log n）。因此，它比简单搜索更快，特别是当您的数据集增长时（算法的增长不是线性的而是对数的，因此相对于O（n）的线性运行时间，它变得更慢）。

另外，二分搜索可以递归写入，但不被视为D＆C算法。尽管较大的输入确实被分解为子集，但如果它们不包含感兴趣的值，则忽略这些子集。不为这些子集生成解决方案，以便它们可以组合以解决更大的输入。

分类

• 选择排序

就像搜索算法的简单搜索一样，选择排序可能是对数据进行排序的最直接，“强力”方式。实际上，您将遍历列表中的每个元素，并按所需顺序将每个元素附加到新列表中。例如，如果您有兴趣对从最大到最小的数字列表进行排序，您会：

1. 搜索列表以查找最大的数字
2. 将该号码添加到新列表中
3. 转到原始列表，再次搜索它以查找下一个最大的数字
4. 将该数字添加到新列表中，依此类推......

对于选择排序，你必须遍历列表中的每个项目（这需要n次，就像进行简单搜索一样）并且你必须这样做n次（不只是一次，因为你必须继续回到原始列表，用于查找要添加到新列表的下一个项目）。因此，这需要O（ñ ²）时间。

• Quicksort

快速排序与选择排序有何不同？如果我们使用数字列表，就像以前一样：

1. 从列表中选择一个元素，称为pivot。在决定快速排序算法的运行速度时，pivot的选择是非常重要的。现在，我们可以每次选择最后一个元素作为pivot。(关于pivot选择的更多信息，我推荐斯坦福Coursera算法课程。)
2. 对列表进行分区，使得小于pivot的所有数字都在其左侧，并且所有大于pivot的数字都在其右侧。
3. 对于列表的每个“half”，您可以将其视为具有新pivot 的新列表，并重新排列每一半，直到它被排序。

快速排序图与数字列表

快速排序是D&C算法的一个例子，因为它将原始列表分成越来越小的有序列表。然后将这些较小的、有序的列表组合起来，得到一个较大的、有序的列表。

Quicksort是独一无二的，因为它的速度取决于pivot选择。在最坏的情况，可能需要O（ñ ²）的时间，这是因为选择排序慢。但是，如果pivot在列表中始终是一个随机元素，则quicksort 平均在O（n log n）时间内运行。

• Mergesort

假设我们仍在使用我们的数字列表。对于合并排序算法，列表将分解为其各个元素。然后从这些元素创建有序对（左边的数字越小）。然后将这些有序对分组为有序的四个组，并且这将继续，直到创建最终合并的排序列表。

mergesort算法的动画概述

与quicksort一样，mergesort是一种D＆C算法，因为输入列表在被组合以生成较大的原始列表的有序版本之前被分解和排序。

Mergesort在O（n log n）时间运行，因为整个列表迭代减半（O（log n））并且这是针对n个项目完成的。

算法和数据结构的知识对数据科学家很有用，因为我们的解决方案不可避免地要用代码编写。因此，理解我们数据的结构以及如何从算法的角度思考非常重要