知道算法的速度和它需要多少空間是很有用的血公。這允許您為工作選擇正確的算法。
O符號給出了一個算法運(yùn)行時間和它使用的內(nèi)存量的粗略指示馏段。當(dāng)有人說, "這個算法有最壞的情況下運(yùn)行時間 O(n^2)和使用 O(n) 空間," 他們的意思是它有點(diǎn)慢, 但不需要大量額外的內(nèi)存堰塌。
計算算法的O通常是通過數(shù)學(xué)分析來完成的涡拘。我們在這里跳數(shù)學(xué),但是, 知道不同的值意味著什么是有用的, 所以這里有一個方便的表疼电。n是指正在處理的數(shù)據(jù)項的數(shù)量嚼锄。例如，當(dāng)排序100個項目的數(shù)組時蔽豺，n＝100区丑。
下面是每一類性能的一些例子：
| Big-O | Name | Description |
|---|---|---|
| O(1) | 恒久不變(constant) | 這是最好的算法 不管有多少數(shù)據(jù)算法總是需要相同的時間量。示例：用索引查找數(shù)組的元素修陡。 |
| O(log n) | 對數(shù)(logarithmic) | 非常好 這些算法在每次迭代中將數(shù)據(jù)量減半沧侥。如果你有100個項目，需要大約7個步驟才能找到答案魄鸦。有1000項, 它需要10個步驟宴杀，1000000項只采取20個步驟。即使對于大量的數(shù)據(jù)拾因，這也是非惩眨快的。示例：二進(jìn)制搜索绢记。 |
| O(n) | 線性(linear) | 良好性能 如果你有100項, 這是100單位的工作扁达，將項目的數(shù)量加倍使得算法花費(fèi)了兩倍長（200個工作單位）。例子：順序搜索蠢熄。 |
| O(n log n) | 線性化(linearithmic) | 體面的表現(xiàn) 這比線性略差跪解，但也不壞。例子：最快的通用排序算法护赊。 |
| O(n^2) | 平方(quadratic) | 有點(diǎn)慢 如果你有100個項目惠遏，這就等于100 ^ 2＝10000個單位的工作。將項目數(shù)加倍使其慢四倍（因為2的平方等于4）骏啰。示例：使用嵌套循環(huán)的算法节吮，如插入排序、冒泡排序判耕。 |
| O(n^3) | 立方(cubic) | 性能不佳 如果你有100項, 這做 100 ^ 3 = 100萬單位的工作透绩。加倍輸入大小使其慢了八倍。例子：矩陣乘法壁熄。 |
| O(n^3) | 立方(cubic) | 性能不佳 如果你有100項, 這做 100 ^ 3 = 100萬單位的工作帚豪。加倍輸入大小使其慢了八倍。例子：矩陣乘法草丧。 |
| O(2^n)) | 指數(shù)級(exponential) | 性能非常差 你想避免這些算法狸臣，但有時你別無選擇。只需在輸入中添加一位即可使運(yùn)行時間加倍昌执。示例: 旅行推銷員問題烛亦。 |
| O(n!) | 階乘(factorial) | 難以忍受的緩慢 做任何事情都需要一百萬年的時間诈泼。 |
O(1)
O(1)復(fù)雜性最常見的例子是訪問數(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ù)雜性的一個例子。
O(n)
for i in stride(from: 0, to: n, by: 1) {
print(array[I])
}
數(shù)組遍歷和線性搜索是O(n)復(fù)雜度的例子檬果。
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)復(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 個磁盤上著名的 "河內(nèi)塔" 問題所需的所有動作。
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!)
函數(shù)的最平凡例子知牌，取O(n!)時間如下祈争。
func nFactFunc(n: Int) {
for i in stride(from: 0, to: n, by: 1) {
nFactFunc(n: n - 1)
}
}
通常, 你不需要數(shù)學(xué)來計算時間復(fù)雜度是多少, 但你可以簡單地使用你的直覺。如果你的代碼使用一個單循環(huán)來查看輸入的所有n個元素角寸，則算法是O(n)菩混。果代碼有兩個嵌套循環(huán)，則為O(n^2)扁藕。三個嵌套循環(huán)給出O(n^3)沮峡，以此類推。
請注意, O 表示法是一個估計, 只是真正有用的大值 n亿柑。例如邢疙，插入排序算法的最壞情況運(yùn)行時間是O(n^2)。在理論上, 比合并排序的運(yùn)行時間差, 即O(n log n)望薄。但是對于少量數(shù)據(jù)疟游，插入排序?qū)嶋H上更快，特別是如果數(shù)組已經(jīng)部分排序了痕支。
如果你覺得這很混亂颁虐，不要讓這個O打擾你太多。當(dāng)比較兩種算法來找出哪一種算法更好時卧须，這是最有用的另绩。但最終你還是想在實踐中檢驗?zāi)囊粋€才是最好的。如果數(shù)據(jù)量相對較小花嘶，那么即使是慢算法也將足夠快用于實際使用笋籽。
