衡量一個算法的空間/時間的復(fù)雜度。
注：具體使用，要根據(jù)對應(yīng)的數(shù)據(jù)量的多次做出選擇。
常用的復(fù)雜度：
O(1)
索引查找
O(log n)
對半查找
O(n)
數(shù)組遍歷和線性搜索
O(n log n）
最快的通用排序算法诅福，合并排序和堆排序
O(n^2）
插入排序
O(2^n）
你想避免這些算法，但有時你別無選擇需忿。僅向輸入添加一位會使運(yùn)行時間加倍诅炉。示例：旅行推銷員問題
O(n!）
階乘 慢得無法忍受。做任何事情都需要一百萬年的時間
以下是每個性能類別的一些示例：
O(1)
復(fù)雜度為 O(1) 的最常見示例是訪問數(shù)組索引屋厘。
let value = array[5]
O(1) 的另一個例子是從堆棧中壓入和彈出涕烧。
O(log n)
var j = 1
while j < n {
// do constant time stuff
j *= 2
}
不是簡單地增加，'j' 在每次運(yùn)行中增加 2 倍汗洒。
二進(jìn)制搜索算法是 O(log n) 復(fù)雜度的一個例子议纯。
在）
for i in stride(from: 0, to: n, by: 1) {
print(array[i])
}
數(shù)組遍歷和線性搜索是 O(n) 復(fù)雜度的例子。
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) 復(fù)雜度的例子溢谤。
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
}
}
遍歷一個簡單的二維數(shù)組和冒泡排序是 O(n^2) 復(fù)雜度的例子瞻凤。
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)
運(yù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)
}
}
在８渭）
下面給出了花費(fèi) O(n!) 時間的最簡單的函數(shù)示例。
func nFactFunc(n: Int) {
for i in stride(from: 0, to: n, by: 1) {
nFactFunc(n: n - 1)
}
}
