工商廣告 III - Big-O
程式的邏輯概念在哪裡?
阿貝你一直說演算邏輯, 我們寫了N年的程式, 也沒寫過半個函數, 需要嗎？ 程式邏輯倒是使用了不少, 真的不知道要用在哪裡？
問題總是接二連三, 早知道就不要那麼麻煩, 講了兩篇的 Python, 搞出了一堆後面的尾巴。現代的年輕人, 毛真多。每個都是碩博士, 小的只有小小的大學畢業而已, 連研究所都沒讀。
早知道, 當年有錢就給它繼續讀下去, 混個文憑也好, 不過阿貝兄弟至少還出個留英派的高材生, 阿貝也沾光。 OK, 言歸正傳, 大家在寫程式, 用了很多外掛函數, 包含原廠標準函數, 其實有很多已經最佳化了, 所以你就很習慣的拿來使用, 例如 Android 的 SDK, 軟體物件包裝起來, 一整包送給你, 無償使用。
但是別忘了 Searching method, memory heap,,,, 等等這類型的 API (SDK) 是基本的功能, 你要運用它, 還是要懂得選擇用那一款, 趕時間, 將就用, 將來程式一大起來, 還是要來檢視問題的, 與其以後找問題, 還不如現在有空先找出來調整一下。
身為一個程式員, 腦袋裡裝著演算邏輯是應該要有的事。既然這樣說, 那主管呢, 是每天在那裡, 準備高爾夫球具準備打球, 每星期對你們的 review 就是問問你程式做到哪裡? 然後就飄走了嗎? 基本上, 阿貝是看過很多主管是醬子的啦, PS: 不要怪他們, 有一天你也會變成他們, 換了位置換了腦袋。
那主管的腦袋到底要裝什麼？當然是對部門的同仁小朋友們做 performance 的了解。以前有一套軟體叫做白金牌 (Platinum)後來被組合國際(CA)併購, 不知道還存在否？阿貝已經很久沒用這些東西了, 那現在呢?單元測試 Unit testing 大行其道, 不過你最好保佑你的老闆看不懂, 這樣測起來就會 煞有其事 的成功執行。
所以說, 做老闆的就要有一套高爾夫工具? 我講錯了, 是一套準則, 好了解工程師的效能。其中之一最有名的就是 時間複雜度 ( Time complexity ), 啥, 讓人覺得無用的東東。真的有效嗎？
時間複雜度 (Time complexity)
唉, 這個中文讓阿貝頭痛了好幾十年, 就好像當年的物件導向 (Object Oriented) [面向對象?] 中文吵了 N 年, TC 依照英文的意思, 是 統籌該程序所產生零碎的時間來做概估程式邏輯的合理性及效能 , 也就是 將時間累加起來, 其中最簡單的就是大歐(Big-O), 我把他再簡單化一點, 我知道教科書都寫的文謅謅的, 搞的大家看書很累, 阿貝也一樣當年只是死記, 也不知道有什麼用, 反正程式裡面開頭加上 begin(time), 結束時加上 end(time) 不就知道了。
嘿嘿, 那我問你一件事, f(n) 函數執行花了10分鐘, 你認為快還是慢？回答的出來才有鬼。沒有比較值如何得知快慢。
Big-O
簡單來說 Big-O 大致分成以下幾個效能評估。我只是深入淺出的解釋, 不要跟我討論細節。 有關它的曲線圖解我就省略, 自己 google 一下, 你們一定看得懂。
-
O(1)
-
O(log n)
-
O(n)
-
其他更細分的東西就不要再深入了, 那個已經是非常嚴謹的學術理論
先定義一下: 什麼是常數 (constant): 1 ,2 ,3 ,3.9 ,200000…000 , , ,等等, 只要是數字的都是, 無論是否有小數點的都算。 什麼是變數 (variable): n ,x ,y23y ,,,, 這些不知道到底是多少數值的, 只有在運算過程中會藏在記憶體裡面。
好啦。
O(1)
例如我們學過的: f(i) := i * 9999 + 9487, f(m) := m + 3 * 120 我們定義的函數 f(i)及f(m) 的式子。
常數, 不予理會, 管他是9萬還是9兆, 只剩下i及m, 想像一下i,m 如果是無限大, 這兩個式子的效能是一樣的, 沒有誰大誰小的情況。 所以我們稱它為大歐(1), 都是 O(1)。
O(n)
基於上面的f(i), 我們加上了迴圈
for(i=0; i<n; i++) {
y = i * 9999 + 9487;
}
這個時候 i 要跑 n 次的迴圈, 所以我們就說是 O(n)
\(O(n^2)\)
再加上一個迴圈
for(i=0; i<n; i++) {
for(j=0; j<n; j++) {
y = j * 9999 + 9487;
}
}
這個時候 i 要跑 n^2 次的迴圈, 所以我們就說是 , 滿累的, 還會有3迴圈以上, 依此類推。
O(log n)
同樣的, 依照 O(n) 的程式改一下
for(i=0; i<n; i++) {
i = i * 2;
y = i * 9999 + 9487;
}
這個時候的變數 i , 提早收工跑玩迴圈, 我們就稱為 O(log n), log 你知道是什麼吧？
對數: 
, 也就是 
好了，以上舉的 n, m, i 都只是隨意取的變數，等號左邊 fn 跟右邊沒有互相呼應的關係存在，請不要讀死書。
結論
身為部門主管, 不需要拿其他的工具來檢測效能, 大致就能看出這個函數的效能是否有利, 程式寫成 O(1) 效能最好, 不過不太可能啦。 但是能寫出 O(log n) 來不就是好棒棒, 所以大家搜尋資料時, 總喜歡用前後逼近的法則, 例如 Binary Search, 只不過現在都有現成的函數在使用, 久而久之程式員就把它當作當然的函數, 結果忘了它的基礎是建立在哪裡!。
留言
張貼留言