大學 & 研究所 & 交換學生 - 所有階段都不務正業
碩一時進了 AR/VR | AutoCAD 實驗室,選修 3D 視覺模擬和虛擬實境,用 unity、cinema 4D 結合 kinect 做手機遊戲寫 JavaScript。
跑到英國找工作的軟體工程師,曾在德國交換,是旅人鄉民島民推特er。分享從撰寫履歷、查詢資料、準備面試到實際面試、國外工作生活的詳細經驗和心路歷程;每天必上 C_Chat 和 Plurk 吸收漫畫動畫能量;同時兼職插畫家、偶而拍拍外拍;心血來潮時翻譯個工程師 meme。
Greedy Algorithm (貪婪演算法) 是指在對問題求解時,總是做出在當前看起來最好的選擇,所以此種演算法在解問題時,不是所有題型都能得到 global optimization (全域最佳解),但對於相當多問題能產生整體最佳解或者是近似整體最佳解。
總之貪婪演算法的精神就是 : 短視近利、今朝有酒今朝醉,每一步面臨選擇時,都做眼前最有利的選擇,不考慮對將來是否有不良的影響,與 dynamic programming 不同,不會保留計算結果。
假設現在有個金額 M,有 1、5、10、20、50 元這些幣值種類,要盡可能用最少的錢幣湊到金額 M。根據貪婪演算法,能用 50 的就盡量用 50 的,否則盡量用 20 的...以此類推;在這種策略下,M 若是 15 則等於 10 * 1 + 5 * 1,共使用了 2 種錢幣。
但是如果我們換一組錢幣的種類如 1、5、11,貪婪演算法可能就不是最佳解。
或是我們有一個最多能背重量為 W 的背包,現在有 N 件物品,每件物品只能用一次且價值不相等,求解將哪些物品裝入背包裡物品價值總和最大,這時候因為要同時考慮重量和價值,也沒辦法用貪婪就取得最佳解。
這在下一篇 Dynamic Programming (動態規劃) 會講解到。
此處談及的 Graph 並不是指圖片或者圖形,而是由數個 vertex (點) 及數條 edgs (邊) 所構成;點與點之間以邊相連,表示這兩點有關聯性。
而一個頂點的 degree (度) 指與該頂點相連的邊的條數。
兩點之間也可以有很多條邊,代表這兩點有很多項關聯;一個點有連到自己的邊,稱之為self-loop (自環),表示自己和自己有關聯。
(https://web.ntnu.edu.tw/~algo/Graph.html)
如果兩張圖的連接方式一模一樣時,則稱作同構圖。圖上的點可以任意移動位置,不論點的位置如何,都不會改變點與點之間的關聯。
遞迴就是在函式之中呼叫函式自己本身,本質上是將複雜的問題,拆分成具有相同性質的子問題,進而解決問題的方法。
一個基本的遞迴函式一定要有:
終止條件 (基本條件)
遞迴條件 (呼叫自己的條件)
如果沒有終止條件,就會無限循環直到當掉。
範例 1 : 假設輸入一個正整數 n,求 1 + 2 + … + n 的總和
我們可以很直覺的使用迭代 (迴圈) 的方式,將所有數字累加在一起。
但因為這個問題能拆成有規律的數個小問題,
如輸入正整數 2 → 1 + 2 = 3
輸入正整數 3 → 1 + 2 + 3 = 6
…
所以這時候就可以使用遞迴來計算。
Time complexity 是 O(n),Space complexity 是 O(1)。
Linked list 是一種常見的資料結構,會包含 head 和 tail 的資訊,以 null 來代表 Linked list 的終點,使用 node 來記錄、表示、儲存資料。
單向鏈結串列 (單鏈結串列、線性鏈結串列、普通鏈結串列) 是最基本的鏈結串列,其特點是鏈結串列的鏈結方向是單向的,對鏈結串列的存取要通過從頭部開始,依序往下讀取。
每個 node 則會包含 value 和 next (Pointer,指向下一個 node 的位置) 的資訊。
(https://vhanda.in/blog/2012/07/shared-memory-hash-table/)
舉例來說,如果我們有 n 個數字要儲存時,通常會用 array 來存。 存好後如果我們拿到另一個數字 37,要判斷這個數字有沒有在 array 裡面,那我們就得跟 array 裡的元素一個個比較,這時 time complexcity 就會是 O(n);下次再換查另一個數字時, time complexcity 又就會是 O(n)。 但如果已經先建立好 hash table,之後如果要查數字 37 時,建立 hash map 時雖然 time complexcity 會是 O(n),但查詢的 time complexcity 就只會是 O(1)。 不過 O(1) 還是理論值,insert、search、lookup、delete 都有可能造成 time complexcity 是 O(n) (請看 example 3) 。
Time complexity 是電腦執行演算法所需要耗費的時間成本,通常會用 O (Big O notation) 去計算。
Big O notation 是解決一個規模為 n 的問題所花費的時間,或者所需步驟之數目;而演算法多快通常不是以秒而是步驟次數來衡量,因為每個人電腦效能會影響執行速度,若用秒數來衡量會顯得不夠客觀。