BIG O NOTATION - Swift Algorithm
現在打算把握自己的時間，一天至少要多吸收一些寫程式的知識，
打算在畢業之後，可以到目標的公司做出很棒的App，
不過當初在大學時候的計算機的課，還是學得不夠深入，總覺得這塊缺了點什麼。
由於訂閱NatashaTheRobot的Newsletter，所以看到一本講解Swift的演算法的書，叫做The Swift Algorithms Book，而如果透過他的推薦碼去購買，有折扣啦，所以我就在這個拮据的狀況，還是買了這本書。
// 想要優惠碼的是可以問我，私下告訴你：）
各位先別買啊，且讓我先讀一讀。
既然花了錢了，就得要看啊，不然可浪費了。
那要看，就得持之以恆囉。
所以預計每天都學一個概念，然後把它記錄在這邊，說不定讀的人也可以受益。
今天要說的主題是，大O，BIG O NOTATION。
這是一個談到演算法，就必定會碰到的一個，大家用來判斷演算法誰快誰慢的一種方式，大概可以這樣解釋。
隨著輸入的N的成長，這個演算法的效率會如何變化，在計算機科學CS當中，就是用BIG O NOTATION去表示，啊....怎麼表示勒。
想要了解它，就讓我們來看看兩種搜尋演算法，應用在排序過的陣列Array上效率的比較吧。
假設要在一個排序過的陣列裡，找到指定的數字：
例如
let numberList : Array<Int> = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Linear Search
這個方法基本上就是暴力算法，就是從第一個一直找到最後一個，就知道有沒有包含那個數。
// 這邊透過extension來給Array新增一個比較的method
extension Array where Element: Comparable {
func linearSearch(forElement key: Element) -> Bool {
//check all possible values
for number in self {
if number == key {
return true
}
}
return false
}
}
//execute search
let isFound: Bool = numberList.linearSearch(forElement: 8)
很明顯的，這種演算法，會隨著陣列的大小，線性的影響搜尋的時間。
如果用大O來表示，就是O(n)
// 如果有不懂什麼叫線性的人要說耶
Binary Search
再來，Binary Search，他是以對數logarithms成長，對數
先讓我們來看看Swift的程式：
extension Array where Element: Comparable {
mutating func binarySearch(forElement key: Element) -> Bool {
var result = false
//establish indices
let min = self.startIndex
let max = self.endIndex - 1
let mid = self.midIndex()
//check bounds
if key > self[max] || key < self[min] {
print("search value \(key) not found..")
return false
}
//evaluate chosen number..
let n = self[mid]
print(String(describing: n) + "value attempted..")
if n > key {
var slice = Array(self[min...mid - 1])
result = slice.binarySearch(forElement: key)
}
else if n < key {
var slice = Array(self[mid + 1...max])
result = slice.binarySearch(forElement: key)
}
else {
print("search value \(key) found..")
result = true
}
return result
}
//returns middle index
func midIndex() -> Index {
return startIndex + (count / 2)
}
}
最後執行它：
//execute search
let isFound: Bool = numberList.binarySearch(forElement: 8)
簡單的敘述的話就是，因為這是個排序過的陣列，所以如果要找的數，比最小的小，或者比最大的大，代表不可能找到答案，直接回答沒有。
而如果可能有，就從中間開始比，好像玩終極密碼一樣，一直切。如果不是中間，比中間大，那就再從中間到最大值之間做一次一樣的事，直到找到為止。
這個方式如果用大O表示，就是O(log n)
我們可以知道這個演算法與Array大小成長的關係，透過O()來表達了。
把它變成圖形的話，就像這樣：
而我們可以看到，在數字小的時候，兩個需要比較的次數是沒什麼差別的，但隨著數字的增加，Binary Search的速度明顯地比線性的要快很多。
在之後的演算法的筆記當中，Big O Notation會是一個基準，要有演算法的思維，就必須先學會這個概念，才能讓我們比較並且找出最有效率以及最有效的手段。
會有一些專有名詞：
- asymptotic analysis : is the process of describing the efficiency of algorithms as their input size (n) grows.
相關連結：
swift-algorithm-club
Reference: Wayne Bishop. “SWIFT ALGORITHMS & DATA STRUCTURES.”
