用動態規劃解決問題:基本觀念(有重疊子問題的問題) 2020 年 7 月 21 日 Magic Len 研究分享、 Go、 Java、 Rust、 演算法、 JavaScript 動態規劃(Dynamic Programming,簡稱DP)是一種解決問題的技巧,主要被用來優化那些「記不住自己過去曾解出來的答案所以只好重複再解」的演算法,讓它們可以「記憶」已經找出來的答案,從而不斷利用,以大大降低時間複雜度(從指數級降到線性)。 繼續閱讀
如何將遞迴函數改成迭代函數? 2020 年 6 月 11 日 Magic Len 研究分享、 Go、 Java、 Rust、 JavaScript 遞迴(Recursive)函數是在執行的過程又會直接或間接地呼叫自己本身的函數。通常透過遞迴函數可以快速地驗證我們的演算法,用簡短的程式碼處理複雜的問題,但是函數在呼叫時需要建立新的堆疊框(Stack Frame),除了會需要額外的開支(Overhead)之外,如果在函數中呼叫函數,而這函數又會呼叫函數,持續下去,很容易就會造成堆疊溢出(Stack Overflow)。雖然有些程式語言的編譯器會做... 繼續閱讀
費氏搜尋(Fibonacci Search)演算法,運用費氏數列的搜尋演算法 2020 年 5 月 28 日 Magic Len 研究分享、 Go、 Java、 Rust、 演算法、 JavaScript 費氏搜尋(Fibonacci Search)演算法有點像是二元搜尋(Binary Search)演算法,同樣是在一個已排序好的陣列中搜尋元素,但是它在移動陣列索引值時是去參考費氏數列(Fibonacci Sequence),而不是像二元搜尋法那樣總是去取索引的中間值。也由於費氏搜尋法在移動陣列索引值時只需要進行加減運算,不需乘、除法,因此它適合被用在不擅長處理乘、除法的CPU上。 繼續閱讀