您需要了解的有关大 O 符号的所有信息 [Python 示例]

目录

🟡 线性时间

🤯 Big O 符号备忘单

读完本文，你将彻底理解大 O 符号。你还将了解如何在现实世界中使用它，甚至了解其背后的数学原理！

在计算机科学中，时间复杂度是描述运行算法所需时间的计算复杂度。

大 O 符号是一种用于确定算法速度的方法。使用大 O 符号，我们可以了解算法是快还是慢。这些知识可以帮助我们设计出更好的算法。

本文使用与 Python 无关的语言编写。这意味着可以轻松将大 O 符号代码移植到 Java 或任何其他语言。如果代码与 Python 无关，则附带 Java 代码。

目录

1. ❓ 我们如何测量算法运行所需的时间？
2. 🤔 什么是大 O 符号？
3. 🟢 恒定时间
4. 🔵 对数时间
5. 🟡 线性时间
6. 🔴多项式时间
7. ❌指数时间
8. 😌 简化大 O 符号
9. ☁ 其他需要学习的重要时刻（但并非必需）
10. 🥇 O（n log n）
11. 👿 O（n！）
12. 🧮 如何通过示例计算我们自己的算法的大 O 符号
13. 🤯 Big O 符号备忘单
14. 🎓 如何计算函数的大 O 符号（离散数学）
15. 👋 摘要

❓ 我们如何测量算法运行所需的时间？

我们可以运行算法 10,000 次并测量所花费的平均时间。

$ python3 -m timeit '[print(x) for x in range(100)]'
100 loops, best of 3: 11.1 msec per loop 
$ python3 -m timeit '[print(x) for x in range(10)]'
1000 loops, best of 3: 1.09 msec per loop
# We can see that the time per loop changes depending on the input!

假设我们有一个算法，它接收一份购物清单并打印出清单上的所有商品。如果清单上有 3 件商品，它会很快执行。但如果清单上有 100 亿件商品，它会花费很长时间。

要“完美”地衡量算法需要多长时间，需要多大的“完美”输入大小？

我们需要考虑的其他事项：

• 存在不同的处理器速度。
• 语言很重要。汇编语言比 Scratch 快；我们该如何看待这一点？

因此，我们使用 Big O（发音为 Big Oh）符号。

🤔 什么是大 O 符号？

大 O 是一种正式的符号，用于描述函数在参数趋向于最大输入时的行为。它由Paul Bachmann、Edmund Landau等人在 1894 年至 19 世纪 20 年代之间发明。20 世纪 70 年代，Donald Knuth对此进行了推广。大 O 取上限。最坏情况会导致算法执行效果最差。对于我们的购物清单示例，最坏情况是无限列表。

我们不会说输入是 100 亿，或者无限大，而是说输入是 n 大小。输入的具体大小并不重要，重要的是我们的算法在最差输入下的表现。即使不知道输入的具体大小，我们仍然可以计算出 Big O。

一旦我们学会了这张表，Big O 就很容易读懂了：

它们越靠右，所需的时间就越长。n是输入的大小。大 O 符号使用这些函数来描述算法效率。

在我们的购物清单示例中，算法的最坏情况是按顺序打印出列表中的每一项。由于n列表中包含多项，因此完成该算法需要 O(n) 的时间复杂度。

其他渐近（时间测量）符号包括：

非正式的说法是：

• Big Omega（最佳情况）
• 大 Theta（平均情况）
• 大 O（最坏情况）

让我们浏览一下“大 O 符号表”中的每一列。

🟢 恒定时间

常数算法不会随着输入规模的变化而变化，无论输入有多大，它们都是常数。例如加法。1 + 2 与 500 + 700 所需的时间相同。它们可能花费更多的物理时间，但我们不会在大数加法的算法中添加更多步骤。底层算法完全保持不变。

我们通常将常数视为 O(1)，但使用任何数字，它仍然是常数。有时我们会将数字改为 1，因为计算所需的步数根本不重要。重要的是它需要常数步数。

恒定时间是所有大O时间复杂度中最快的。恒定时间的正式定义是：

它的上限是一个常数

例如：

def OddOrEven(n):
    return "Even" if n % 2 else "Odd"

或者用 Java 来写：

boolean isEven(double num) { return ((num % 2) == 0); }

在大多数编程语言中，所有整数都有上限。基本运算（例如模运算%）都受此上限限制。如果超出此上限，就会出现溢出错误。

由于这个上限，它满足 O(1)。

🔵 对数时间

这里简要解释一下对数的含义。

对数_{3} ^{9}

这里问的是“3 的几次方等于 9？”也就是说 3 的 2 次方等于 9，所以整个表达式如下所示：

Log_{3} ^{9} = 2

对数算法每次运行时都会将列表减半。

让我们看一下二分查找。给定以下排序列表：

a = [1, 2, 3, 4, 5, 6 , 7, 8, 9, 10]

我们想找到数字“2”。

我们将二分查找实现为：

def binarySearch(alist, item):
    first = 0
    last = len(alist)-1
    found = False

    while first <= last and not found:
        midpoint = (first + last)//2
        if alist[midpoint] == item:
            found = True
        else:
            if item < alist[midpoint]:
            last = midpoint-1
            else:
                first = midpoint+1

    return found

用英语来说就是：

• 转到列表中间
• 检查该元素是否是答案
• 如果不是，检查该元素是否大于我们想要查找的项目
• 如果是，则忽略列表的右侧（所有高于中点的数字）并选择一个新的中点。
• 重新开始，找到新列表中的中点。

该算法每次迭代都会将输入减半。因此，它是对数函数。其他示例包括：

• 斐波那契数列计算
• 搜索二叉搜索树
• 搜索 AVL 树

🟡 线性时间

线性时间算法意味着输入中的每个元素都被访问一次，即 O(n) 次。随着输入的大小 N 的增长，我们算法的运行时间也与输入的大小成正比。

线性运行时间算法非常普遍。线性运行时间意味着程序会访问输入中的每个元素。线性时间复杂度 O(n) 意味着随着输入的增长，算法的完成时间会相应延长。2019 年 4 月 2 日

还记得我们之前的购物清单应用吗？该算法的运行时间为 O(n)，也就是线性时间！

线性时间是指在最坏的情况下，列表中的每个项目都会被访问一次。

为了读出购物清单，我们的算法必须读出每件商品。它不能只读出清单的一半，也不能添加我们未添加的商品。它必须一次列出所有 n 件商品。

shopping_list = ["Bread", "Butter", "The Nacho Libre soundtrack from the 2006 film Nacho Libre", "Reusable Water Bottle"]
for item in shopping_list:
    print(item)

我们来看另一个例子。

未排序数组的最大项

给出列表：

a = [2, 16, 7, 9, 8, 23, 12]

我们如何计算出最大的物品是什么？

我们需要像这样编程：

a = [2, 16, 7, 9, 8, 23, 12]
max_item = a[0]
for item in a:
    if item > max_item:
        max_item = item

我们必须逐一检查列表中的每个项目。

🔴多项式时间

多项式时间是输入的多项式函数。多项式函数看起来像 n²^或n³^等等。

如果循环一次列表的复杂度为 O(n)，那么循环两次必然为 O(n ^2)。每次循环都会遍历列表一次。对于列表中的每个元素，我们都会遍历整个列表一次。最终共计 n ^{2 次}操作。

a = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
for i in a:
    for x in a:
        print("x")

对于同一列表上的每个嵌套，都会在幂上额外添加 +1。

因此三重嵌套循环为 O(n ^3)。

冒泡排序是 O(n² ⁾算法的一个很好的例子。该排序算法取第一个数字，如果它们的顺序错误，则将其与相邻的数字交换。它会对每个数字执行此操作，直到所有数字都按正确顺序排列，从而完成排序。

def bubbleSort(arr):
    n = len(arr)

    # Traverse through all array elements
    for i in range(n):

        # Last i elements are already in place
        for j in range(0, n-i-1):

            # traverse the array from 0 to n-i-1
            # Swap if the element found is greater
            # than the next element
            if arr[j] > arr[j+1] :
                arr[j], arr[j+1] = arr[j+1], arr[j]

# Driver code to test above
arr = [64, 34, 25, 12, 22, 11, 90]

bubbleSort(arr)

附注：我的教授将任何时间等于或大于多项式的算法称为：

彻头彻尾的灾难！这简直是一场灾难！一场浩劫！

但时间复杂度高的事情往往向我们表明某些事情可以加快。

比如我遇到的一个问题。给定一个句子，其中有多少个单词在英语词典中出现？我们可以想象一个 O(n^ ^{2) 的}方法。一遍遍地for loop查找句子，一遍遍地查找词典。

dictionary = ["a", "an"] # imagine if this was the dictionary
sentence = "hello uu988j my nadjjrjejas is brandon nanndwifjasj banana".split(" ")

counter = 0
for word in sentence:
    for item in dictionary:
        if word == item:
            counter = counter + 1

O(n² ^)！简直是灾难！不过，知道这是灾难，意味着我们可以加快速度。字典默认是排序的。如果我们对句子中的单词列表进行排序，并以此方式检查每个单词，会怎么样？我们只需要循环遍历字典一次。如果我们要检查的单词小于字典中当前单词的个数，我们就切换到列表中的第二个单词。

现在我们的算法复杂度是 O(n log n)。我们意识到这并不是什么灾难，所以我们可以继续前进！了解时间复杂度不仅在面试中有用，它还是改进算法的重要工具。

我们可以利用算法设计知识来加速我们构建的许多多项式算法。

❌指数时间

指数时间为 2 ^n，其中 2 取决于所涉及的排列。

这个算法是所有算法中最慢的。你也看到了我的教授对多项式算法的反应。他对指数算法简直气得跳脚！

举个例子，假设我们有一个仅由数字组成的密码（即 10 个数字，从 0 到 9）。我们想要破解一个长度为 n 的密码，因此要强行破解每个组合，我们需要：10 ⁿ

要进行的组合。

指数时间的一个例子是找到一个集合的所有子集。

>>> subsets([''])
['']
>>> subsets(['x'])
['', 'x']
>>> subsets(['a', 'b'])
['', 'a', 'b', 'ab']

我们可以看到，当输入大小为 2 时，输出大小为 2 ² = 4。

现在，让我们开始编码subsets。

from itertools import chain, combinations

def subsets(iterable):
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

摘自 itertools 文档。这里重点在于，它随着输入大小呈指数增长。Java代码可在此处找到。

指数算法很可怕，但就像多项式算法一样，我们也能学到一些东西。假设我们要计算 10 ^{^4，}我们需要这样做：

10 * 10 * 10 * 10 = 10 ² * 10 ²

我们必须计算两次 10 ^{^2}！如果我们把这个值存储在某个地方，以后再用，就不用重新计算了，会怎么样？这就是动态规划的原理，你可以在这里阅读。

当我们看到指数算法时，通常可以使用动态规划来加速它。

再次，了解时间复杂度可以让我们构建更好的算法。

这是我们的 Big O 符号图，其中数字减少了，因此我们可以看到所有不同的线。

您可以在此处找到此图表的代码。

😌 简化大 O 符号

时间复杂度很少像计算有多少个 for 循环那么简单。如果我们的算法看起来像 O(n + n ^{2) 会怎么样？}我们可以使用以下简单规则简化算法：

删除常量

如果我们有一个描述为 O(2n) 的算法，我们去掉 2，这样它就变成了 O(n)。

删除非主导术语

O(n² + n) 变为 O(n²)。 Big O 中只保留较大的那个。

如果我们有一个和，例如 O(b² + a)，我们不能在不知道 b 和 a 是什么的情况下放弃任何一个。

就这样吗？

是的！最难的部分是先弄清楚我们程序的复杂度。简化其实很容易！只要记住大 O 符号的黄金法则：

“最糟糕的情况是什么？”

☁ 其他需要学习的重要时刻（但并非必需）

🥇 O（n log n）

这是比较排序最快的时间。除非使用一些特殊属性，例如基数排序，否则无法再加快速度。O(n log n) 是最快的比较排序时间。

归并排序相当出名，因为它的复杂度为 O(n log n)。归并排序之所以是一个优秀的算法，不仅因为它排序速度快，还因为它的思想被用来构建其他算法。

归并排序用于教授分治算法。它本身就是一种非常棒的排序算法，其根源并不局限于排序。

归并排序的工作原理是将数字列表分解成单个数字：

然后在合并之前对每个列表进行排序：

def mergeSort(alist):
    print("Splitting ",alist)
    if len(alist)>1:
        mid = len(alist)//2
        lefthalf = alist[:mid]
        righthalf = alist[mid:]

        mergeSort(lefthalf)
        mergeSort(righthalf)

        i=0
        j=0
        k=0
        while i < len(lefthalf) and j < len(righthalf):
            if lefthalf[i] <= righthalf[j]:
                alist[k]=lefthalf[i]
                i=i+1
            else:
                alist[k]=righthalf[j]
                j=j+1
            k=k+1

        while i < len(lefthalf):
            alist[k]=lefthalf[i]
            i=i+1
            k=k+1

        while j < len(righthalf):
            alist[k]=righthalf[j]
            j=j+1
            k=k+1
    print("Merging ",alist)

alist = [54,26,93,17,77,31,44,55,20]
mergeSort(alist)
print(alist)

点击此处了解有关 Mergesort 的更多信息。

👿 O（n！）

注意到le10顶部了吗？这个太大了，以至于其他时间看起来都一样！

这个时间复杂度经常被拿来开玩笑，指的是博哥排序。我还没找到一个现实生活中（不是开玩笑）的 O(n!) 算法，它不是计算 O(6!) 之类的复杂度的算法。

🧮 如何通过示例计算我们自己的算法的大 O 符号

我们自己的算法通常会基于一些已经拥有大 O 符号的著名算法。如果没有，也不用担心！计算出我们算法的大 O 符号很容易。

试想一下：

“对于我的程序来说，绝对最差的输入是什么？”

以顺序搜索算法为例。

def search(listInput, toFind):
    for counter, item in enumerate(listInput):
        if toFind == item:
            return (counter, item)
    return "did not find the item!"

最好的输入是：

search(["apples"], "apples")

但最糟糕的输入是如果该项目位于长列表的末尾。

search(["apples", "oranges", "The soundtrack from the 2006 film Nacho Libre", "Shrek"], "Shrek")

最坏的情况是 O(n)，因为我们必须遍历列表中的每个项目才能找到它。

如果我们的搜索算法是二分查找会怎么样？我们知道二分查找每次都会把列表分成两半。听起来像log n！

如果我们的二分搜索寻找一个对象，然后寻找其他类似的对象会怎么样？

# here we want to find the film shrek, find its IMDB rating and find other films with that IMDB rating. We are using binary search, then sequential search
toFind = {title: "Shrek", IMDBrating: None}
ret = search(toFind)
ret = search(ret['IMDBrating'])

我们找到了 IMDB 评分为 7.8 的《怪物史莱克》。但我们只按片名排序，而不是按 IMDB 评分排序。我们必须使用顺序搜索来查找所有其他具有相同评分的电影。

二分查找的复杂度为 O(log n)，顺序查找的复杂度为 O(n)，这使得我们的算法复杂度为 O(n log n)。这并非灾难，因此我们可以肯定这不是一个糟糕的算法。

即使我们的算法与其他算法并非严格相关，我们仍然可以将它们与我们已知的算法进行比较。O(log n) 表示减半。O(n ²⁾表示嵌套 for 循环。

最后一点，我们并不总是处理n。请看下面的算法：

x = [1, 2, 3, 4, 5]
y = [2, 6]
y = iter(y)
counter = 0
total = 0.0
while counter != len(x):
    # cycles through the y list.
    # multiplies 2 by 1, then 6 by 2. Then 2 by 3. 
    total = total + x[counter] * next(y)
    counter += 1
print(total)

我们有两个输入：x 和 y。因此，我们的符号为 O(x + y)。有时，如果不了解更详细的数据，我们无法缩小符号的长度。

🤯 Big O 符号备忘单

我给你做了一张小信息图！“每个嵌套的 for 循环加 1”依赖于 for 循环，就像我们之前看到的一样。不过，一遍一遍地解释这些会占用太多空间 😅

🎓 如何计算函数的大 O 符号（离散数学）

不幸的是，Dev 不支持 MathJax :-( 所以文章的这一部分无法包含 :'( 单击此处查看全文

👋 摘要

大 O 代表算法所需的时间，但有时我们也会关心算法占用的内存（空间复杂度）。如果您遇到问题，请返回此页面并查看信息图！