衡量一个算法的空间/时间的复杂度。
注：具体使用，要根据对应的数据量的多次做出选择。

常用的复杂度：

O(1)

索引查找

O(log n)

对半查找

O(n)

数组遍历和线性搜索

O(n log n）

最快的通用排序算法，合并排序和堆排序

O(n^2）

插入排序

O(2^n）

你想避免这些算法，但有时你别无选择。仅向输入添加一位会使运行时间加倍。示例：旅行推销员问题

O(n!）

阶乘 慢得无法忍受。做任何事情都需要一百万年的时间

image.png

以下是每个性能类别的一些示例：

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) 复杂度的一个例子。

在）

for i in stride(from: 0, to: n, by: 1) {
print(array[i])
}
数组遍历和线性搜索是 O(n) 复杂度的例子。

O（n日志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)
solveHanoi(n: n - 1, from: spare, to: to, spare: from)
}
}
在！）

下面给出了花费 O(n!) 时间的最简单的函数示例。

func nFactFunc(n: Int) {
for i in stride(from: 0, to: n, by: 1) {
nFactFunc(n: n - 1)
}
}