如何設計演算法？下面這篇文章來跟大家分析一下常見的演算法範式。有一定的參考價值，有需要的朋友可以參考一下，希望對大家有幫助。
先明確三個概念：
演算法： 依步驟解決問題的過程。
範式： 思考問題的模式。
演算法範式： 為問題建立高效解決方案的常規方法。
本文討論一些常用的演算法範式，例如
在排序演算法中，合併和快速排序這兩種演算法的共同點就是分而治之的演算法。
分而治之
是一種常見的演算法設計，它的思路是把問題分解為與原始問題相似的較小子問題。通常以遞歸方式解決子問題，並結合子問題的解決方案來解決原始問題。
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);
}以下是用分治實現的二元搜尋。 binarySearchbinarySearchRecursive
動態規劃法動態規劃
是一種最佳化技術，用於透過把複雜問題分解為較小的子問題來解決。看起來很像是分治法，但動態規劃不是把問題分解為獨立的子問題然後再組合在一起，而是只把問題分解為獨立的
子問題。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 毛錢。 coinscachemakeChange在上面的程式碼中，參數 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中文網其他相關文章！
