大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"的计数器,值为1i <= 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