下面的例子都使用了Python编写的代码。请注意,这不是一个完整的Big O类型列表。
恒定
O ( 1 ) {\displaystyle O(1)}
。无论输入多少,总是需要相同的时间。例如,接受一个整数(称为x)并返回双倍值的函数。
def double(x): return x * 2 #返回x乘以2的值。
在接受输入后,这个函数总是一步一步地返回输出。它是常数,因为它总是需要相同的时间,所以它是O ( 1 ) {\displaystyle O(1)}
。
直线型
O ( n ) {\displaystyle O(n)}
.根据输入的大小增加,用n {\displaystyle n
}表示。让我们假设一个函数接受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}。
,需要5个循环才能完成。同理,如果我们输入100,它将输出1,2,3...98,99,100 {\displaystyle 1,2,3...98,99,100}
,需要100个循环才能完成。如果输入的是n个{displaystyle n}
,那么该算法的运行时间正好是n个{displaystyle n
}循环,每次都是如此,因此它是O ( n ) {displaystyle O(n)}
。
系数
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}
项目(或5 ! {\displaystyle 5!}
)。如果我们的输入是n个{displaystyle n}
城市长,那么输出的数量是n !{displaystyle n! }
; 换句话说,假设我们通过每一个排列组合,我们将需要O ( n ! ) {displaystyle O(n!)}
循环来完成它。