大O符号

大O记法是一种比较算法的方法。它通过计算需要多少内存和完成需要多少时间来比较它们。

大O记号法经常用于识别一个问题的复杂程度，也称为问题的复杂度等级。数学家保罗-巴赫曼（Paul Bachmann，1837-1920）在1896年出版的《分析法》（Analytische Zahlentheorie）一书的第二版中，是第一个使用这种符号的人。埃德蒙-兰道（Edmund Landau，1877-1938）使这种记法流行起来。因此，当人们谈论兰道符号时，他们会提到这个符号。

大O记数法是以"函数的阶数"来命名的，它指的是函数的增长。大O记数法是用来寻找函数增长速度的上界（可能的最高量），也就是说它计算出将输入变成输出所需的最长时间。这意味着在最坏的情况下，每次都会走最长的路线，可以按照算法所能花费的时间来分组。

大O是一种表达式，它可以找到最坏情况下的运行时间，显示一个算法的效率，而不必在计算机上运行程序。这也很有用，因为不同的计算机可能有不同的硬件，因此需要不同的时间来完成它。由于Big O总是假设最坏情况，它可以显示出一致的速度测量：无论你的硬件如何，O ( 1 ) {\displaystyle O(1)}{\displaystyle O(1)}总是要比O ( n !){\displaystyle O(n!)}完成得更快{\displaystyle O(n!)}，因为它们的效率水平不同。

例子

下面的例子都使用了Python编写的代码。请注意，这不是一个完整的Big O类型列表。

恒定

O ( 1 ) {\displaystyle O(1)}{\displaystyle O(1)} 。无论输入多少，总是需要相同的时间。例如，接受一个整数（称为x）并返回双倍值的函数。

def double(x): return x * 2 #返回x乘以2的值。

在接受输入后，这个函数总是一步一步地返回输出。它是常数，因为它总是需要相同的时间，所以它是O ( 1 ) {\displaystyle O(1)}{\displaystyle O(1)}。

直线型

O ( n ) {\displaystyle O(n)}{\displaystyle O(n)} .根据输入的大小增加，用n {\displaystyle nn}表示。让我们假设一个函数接受n，并返回从1到n的每个数字。

def count(n): i = 1 #创建一个名为"i"的计数器，值为1，而i <= n。#当i小于或等于n时 print(i) #打印i的值 i = i + 1 #重新定义i为"i + 1的值"

如果我们输入5的值，那么将输出1，2，3，4，5 {\displaystyle 1，2，3，4，5}。{\displaystyle 1,2,3,4,5}，需要5个循环才能完成。同理，如果我们输入100，它将输出1，2，3...98，99，100 {\displaystyle 1,2,3...98,99,100}{\displaystyle 1,2,3...98,99,100} ，需要100个循环才能完成。如果输入的是n个{displaystyle n}n，那么该算法的运行时间正好是n个{displaystyle nn}循环，每次都是如此，因此它是O ( n ) {displaystyle O(n)}{\displaystyle O(n)}。

系数

O ( n ! ) {/displaystyle O(n!)}{\displaystyle O(n!)} 。以因子量增加，意味着所需时间随着输入量的增加而大量增加。例如，假设我们希望参观世界上的五个城市，并希望看到每一个可能的排序（permutation）。我们可以用Python的itertools库写一个算法如下。

import itertools #导入itertools库 cities = ['London', 'Paris', 'Berlin', 'Amsterdam', 'Rome'] #一个我们选择的城市数组 def permutations(cities):#输入一个城市数组: for i in itertools. permutations(cities):#对于我们项目的每一个排列组合(分配给变量"i") print(i) #输出i。

该算法将计算我们城市的每一个独特的排列组合，然后将其输出。输出的例子将包括：

('伦敦'、'巴黎'、'柏林'、'阿姆斯特丹'、'罗马')('伦敦'、'巴黎'、'柏林'、'罗马'、'阿姆斯特丹')('伦敦'、'巴黎'、'阿姆斯特丹'、'柏林'、'罗马')......。('罗马'、'阿姆斯特丹'、'巴黎'、'柏林'、'伦敦') ('罗马'、'阿姆斯特丹'、'柏林'、'伦敦'、'巴黎') ('罗马'、'阿姆斯特丹'、'柏林'、'巴黎'、'伦敦')

这里我们的输入列表有5个项目，每选择一个，我们的剩余选项就减少1个。换句话说，我们的5个输入选择5×4×3×2×1 {\displaystyle 5\times 4\times 3\times 2\times 1}{\displaystyle 5\times 4\times 3\times 2\times 1}项目（或5 ! {\displaystyle 5!}{\displaystyle 5!}）。如果我们的输入是n个{displaystyle n}n城市长，那么输出的数量是n !{displaystyle n! } {\displaystyle n!}; 换句话说，假设我们通过每一个排列组合，我们将需要O ( n ! ) {displaystyle O(n!)}{\displaystyle O(n!)}循环来完成它。

小欧记事法

大O的一个更严格的版本是little-o。大O和little-o的区别在于little-o是一个严格的上限：O ( n ) {\displaystyle O(n)}{\displaystyle O(n)}意味着完成时间会根据输入大小增加到这个最大值，而o ( n ) {\displaystyle o(n)}{\displaystyle o(n)}意味着完成时间一般会在这个时间量之下。换句话说，Big O假设每个循环都会走最长的路径，过程时间会尽可能长，而little-o对实际运行时间更现实；如果循环次数是基于掷6面骰子，Big O会一直假设掷出6，而little-o会考虑其他数字被掷出的同等概率。

问题和答案

问：什么是大O记号？
答：大O符号法是一种比较不同函数增长率的方法，通常用来比较不同算法的效率，计算完成所需的内存和时间。它也可以用来识别一个问题的复杂程度。

问：谁是第一个使用这种符号的人？
答：数学家保罗-巴赫曼（Paul Bachmann，1837-1920）在他1896年出版的《分析法》（Analytische Zahlentheorie）一书中，是第一个使用这种符号法。

问：大O代表什么？
答：大O代表 "函数的阶数"，指的是函数的增长速度。

问：大O是如何使用的？
答：Big O符号用于寻找函数增长率的上界（可能的最高量），这意味着它计算出将输入转化为输出所需的最长时间。这意味着算法可以按照它们在最坏情况下所需的时间进行分组，在这种情况下，每次都会采取最长的路线。

问：什么是兰道符号？
答：兰道符号指的是大O符号，以埃德蒙-兰道（1877-1938）命名，他使这种符号流行起来。
问：大O为什么有用？

答：Big O允许我们在不需要在计算机上运行程序的情况下测量速度，因为它总是假设最坏的情况，使得它与计算机之间的硬件差异一致。它还显示了一种算法的效率，而不需要在计算机上实际运行它。

AlegsaOnline.com - 2020 / 2023 - License CC3