衡量一个算法的空间/时间的复杂度。
注：具体使用，要根据对应的数据量的多次做出选择。
常用的复杂度：
O(1)
索引查找
O(log n)
对半查找
O(n)
数组遍历和线性搜索
O(n log n）
最快的通用排序算法，合并排序和堆排序
O(n^2）
插入排序
O(2^n）
你想避免这些算法，但有时你别无选择。仅向输入添加一位会使运行时间加倍。示例：旅行推销员问题
O(n!）
阶乘 慢得无法忍受。做任何事情都需要一百万年的时间
以下是每个性能类别的一些示例：
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)
}
}
