如何設計演算法?下面這篇文章來跟大家分析一下常見的演算法範式。有一定的參考價值,有需要的朋友可以參考一下,希望對大家有幫助。
先明確三個概念:
演算法: 依步驟解決問題的過程。
範式: 思考問題的模式。
演算法範式: 為問題建立高效解決方案的常規方法。
本文討論一些常用的演算法範式,例如
在排序演算法中,合併和快速排序這兩種演算法的共同點就是分而治之的演算法。
分而治之
是一種常見的演算法設計,它的思路是把問題分解為與原始問題相似的較小子問題。通常以遞歸方式解決子問題,並結合子問題的解決方案來解決原始問題。function binarySearchRecursive(array, value, low, high) { if (low <= high) { const mid = Math.floor((low + high) / 2); const element = array[mid]; if (element < value) { return binarySearchRecursive(array, value, mid + 1, high); } else if (element > value) { return binarySearchRecursive(array, value, low, mid - 1); } else { return mid; } } return null; } export function binarySearch(array, value) { const sortedArray = quickSort(array); const low = 0; const high = sortedArray.length - 1; return binarySearchRecursive(array, value, low, high); }
以下是用分治實現的二元搜尋。 binarySearch
binarySearchRecursive
動態規劃法動態規劃
是一種最佳化技術,用於透過把複雜問題分解為較小的子問題來解決。看起來很像是分治法,但動態規劃不是把問題分解為獨立的子問題然後再組合在一起,而是只把問題分解為獨立的
子問題。function minCoinChange(coins, amount) { const cache = []; const makeChange = (value) => { if (!value) { return []; } if (cache[value]) { return cache[value]; } let min = []; let newMin; let newAmount; for (let i = 0; i < coins.length; i++) { const coin = coins[i]; newAmount = value - coin; if (newAmount >= 0) { newMin = makeChange(newAmount); } if (newAmount >= 0 && (newMin.length < min.length - 1 || !min.length) && (newMin.length || !newAmount)) { min = [coin].concat(newMin); } } return (cache[value] = min); } return makeChange(amount); }
這是一個名為為硬幣找零問題的常見面試題。硬幣找零問題是給定找零的金額,找出可以用多少特定數量的硬幣來找零的方式。最小硬幣找零問題只是找到使用給定面額的錢所需的最少硬幣數量。例如,如果需要找零 3 毛 7 分,則可以使用 1 個 2 分,1個 5 分,1 個 1 毛錢和1個 2 毛錢。 coins
cache
makeChange
在上面的程式碼中,參數 cache
表示面額(在人民幣中為 [1, 2, 5, 10, 20, 50])。為了防止重複計算,用到了一個
console.log(minCoinChange([1, 2, 5 10, 20], 37)); // => [2, 5, 10, 20] console.log(minCoinChange([1, 3, 4], 6)) // => [3, 3]
貪心演算法
function minCoinChange(coins, amount) { const change = []; let total = 0; for (let i = coins.length; i>= 0; i--) { const coin = coins[i]; while (total + coin <= amount) { change.push(coin); total += coin; } } return change; }
上面用動態規劃解決的硬幣問題也可以用貪心演算法解決。這個解的是否能得到最優解取決於所採用的面額。
console.log(minCoinChange([1, 2, 5 10, 20], 37)); // => [2, 5, 10, 20] console.log(minCoinChange([1, 3, 4], 6)) // => [4, 1, 1]
可以看到,貪心演算法比動態規劃的方案簡單許多。下面看一下同樣的求解案例,來了解兩者之間的差異:[3,3]
貪心演算法給出了第一個問題的最優解,但第二個並不是最優解(應該是
)。 貪心演算法比動態規劃演算法簡單且更快,但是得到的有可能不是最優解。回溯演算法
如果它不起作用,就回溯並重複步驟 1,直到找到合適的解決方案為止。
對於回溯演算法,我會另寫一篇文章來介紹更複雜的演算法。究竟寫什麼我還沒想好,也許是寫一個對數獨求解的程序,如果你對這個感興趣,請關注我的公眾號!演算法是永無止境的,希望這篇文章能幫你了解一些常見的演算法範式。 相關免費學習推薦:
js影片教學
以上是如何設計演算法?常見的演算法範式介紹的詳細內容。更多資訊請關注PHP中文網其他相關文章!