知道算法的速度和它需要多少空间是很有用的。这允许您为工作选择正确的算法。
O符号给出了一个算法运行时间和它使用的内存量的粗略指示。当有人说, "这个算法有最坏的情况下运行时间 O(n^2)和使用 O(n) 空间," 他们的意思是它有点慢, 但不需要大量额外的内存。
计算算法的O通常是通过数学分析来完成的。我们在这里跳数学,但是, 知道不同的值意味着什么是有用的, 所以这里有一个方便的表。n是指正在处理的数据项的数量。例如，当排序100个项目的数组时，n＝100。
下面是每一类性能的一些例子：
| Big-O | Name | Description |
|---|---|---|
| O(1) | 恒久不变(constant) | 这是最好的算法 不管有多少数据算法总是需要相同的时间量。示例：用索引查找数组的元素。 |
| O(log n) | 对数(logarithmic) | 非常好 这些算法在每次迭代中将数据量减半。如果你有100个项目，需要大约7个步骤才能找到答案。有1000项, 它需要10个步骤，1000000项只采取20个步骤。即使对于大量的数据，这也是非常快的。示例：二进制搜索。 |
| O(n) | 线性(linear) | 良好性能 如果你有100项, 这是100单位的工作，将项目的数量加倍使得算法花费了两倍长（200个工作单位）。例子：顺序搜索。 |
| O(n log n) | 线性化(linearithmic) | 体面的表现 这比线性略差，但也不坏。例子：最快的通用排序算法。 |
| O(n^2) | 平方(quadratic) | 有点慢 如果你有100个项目，这就等于100 ^ 2＝10000个单位的工作。将项目数加倍使其慢四倍（因为2的平方等于4）。示例：使用嵌套循环的算法，如插入排序、冒泡排序。 |
| O(n^3) | 立方(cubic) | 性能不佳 如果你有100项, 这做 100 ^ 3 = 100万单位的工作。加倍输入大小使其慢了八倍。例子：矩阵乘法。 |
| O(n^3) | 立方(cubic) | 性能不佳 如果你有100项, 这做 100 ^ 3 = 100万单位的工作。加倍输入大小使其慢了八倍。例子：矩阵乘法。 |
| O(2^n)) | 指数级(exponential) | 性能非常差 你想避免这些算法，但有时你别无选择。只需在输入中添加一位即可使运行时间加倍。示例: 旅行推销员问题。 |
| O(n!) | 阶乘(factorial) | 难以忍受的缓慢 做任何事情都需要一百万年的时间。 |
O(1)
O(1)复杂性最常见的例子是访问数组索引。
let value = array[5]
O(1)的另一个例子是从栈中推送和弹出。
O(log n)
var j = 1
while j < n {
// do constant time stuff
j *= 2
}
"j" 不是简单地递增, 而是在每次运行时增加2倍。
二进制搜索算法是O(log n)复杂性的一个例子。
O(n)
for i in stride(from: 0, to: n, by: 1) {
print(array[I])
}
数组遍历和线性搜索是O(n)复杂度的例子。
O(n log n)
for i in stride(from: 0, to: n, by: 1) {
var j = 1
while j < n {
j *= 2
// do constant time stuff
}
}
或者
for i in stride(from: 0, to: n, by: 1) {
func index(after i: Int) -> Int? { // multiplies `i` by 2 until `i` >= `n`
return i < n ? i * 2 : nil
}
for j in sequence(first: 1, next: index(after:)) {
// do constant time stuff
}
}
合并排序和堆排序是O(n log n)复杂性的示例。
O(n^2)
for i in stride(from: 0, to: n, by: 1) {
for j in stride(from: 1, to: n, by: 1) {
// do constant time stuff
}
}
遍历一个简单的二维数组和冒泡排序是O(n^2)复杂度的例子。
O(n^3)
for i in stride(from: 0, to: n, by: 1) {
for j in stride(from: 1, to: n, by: 1) {
for k in stride(from: 1, to: n, by: 1) {
// do constant time stuff
}
}
}
O(2^n)
运行时间O(2^N)的算法通常是递归算法，通过递归求解两个较小的n-1个问题来解决n的问题。下面的示例打印出解决 N 个磁盘上著名的 "河内塔" 问题所需的所有动作。
func solveHanoi(n: Int, from: String, to: String, spare: String) {
guard n >= 1 else { return }
if n > 1 {
solveHanoi(n: n - 1, from: from, to: spare, spare: to)
} else {
solveHanoi(n: n - 1, from: spare, to: to, spare: from)
}
}
O(n!)
函数的最平凡例子，取O(n!)时间如下。
func nFactFunc(n: Int) {
for i in stride(from: 0, to: n, by: 1) {
nFactFunc(n: n - 1)
}
}
通常, 你不需要数学来计算时间复杂度是多少, 但你可以简单地使用你的直觉。如果你的代码使用一个单循环来查看输入的所有n个元素，则算法是O(n)。果代码有两个嵌套循环，则为O(n^2)。三个嵌套循环给出O(n^3)，以此类推。
请注意, O 表示法是一个估计, 只是真正有用的大值 n。例如，插入排序算法的最坏情况运行时间是O(n^2)。在理论上, 比合并排序的运行时间差, 即O(n log n)。但是对于少量数据，插入排序实际上更快，特别是如果数组已经部分排序了。
如果你觉得这很混乱，不要让这个O打扰你太多。当比较两种算法来找出哪一种算法更好时，这是最有用的。但最终你还是想在实践中检验哪一个才是最好的。如果数据量相对较小，那么即使是慢算法也将足够快用于实际使用。
