如何設計演算法？常見的演算法範式介紹

如何設計演算法？下面這篇文章來跟大家分析一下常見的演算法範式。有一定的參考價值，有需要的朋友可以參考一下，希望對大家有幫助。

先明確三個概念：

演算法： 依步驟解決問題的過程。

範式： 思考問題的模式。

演算法範式： 為問題建立高效解決方案的常規方法。

本文討論一些常用的演算法範式，例如

• 分治演算法
• 動態規劃
• 貪婪演算法
• 動態規劃

貪婪演算法

分治法

在排序演算法中，合併和快速排序這兩種演算法的共同點就是分而治之的演算法。

分而治之

是一種常見的演算法設計，它的思路是把問題分解為與原始問題相似的較小子問題。通常以遞歸方式解決子問題，並結合子問題的解決方案來解決原始問題。

1. 分治法的邏輯可以分為三個步驟：
2. 將原始問題分成較小的子問題。
3. 透過遞歸解決子問題，解決完畢之後返回子問題的解決方案。

將子問題的解決方案合併為原始問題的解決方案。

分治法的例子：二元搜尋

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

請注意，上面的

函數是供他人呼叫的，而

是實現分治法的地方。

動態規劃法動態規劃

是一種最佳化技術，用於透過把複雜問題分解為較小的子問題來解決。看起來很像是分治法，但動態規劃不是把問題分解為獨立的子問題然後再組合在一起，而是只把問題分解為

獨立的

子問題。

1. 演算法邏輯分為三個步驟：
2. 定義子問題。
3. 重複解決子問題。

辨識並解決基本問題。

動態規劃案例：最小硬幣找零問題

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. 非常適合逐步尋找和建立解決方案。
2. 嘗試以一種方式解決問題。

如果它不起作用，就回溯並重複步驟 1，直到找到合適的解決方案為止。

對於回溯演算法，我會另寫一篇文章來介紹更複雜的演算法。究竟寫什麼我還沒想好，也許是寫一個對數獨求解的程序，如果你對這個感興趣，請關注我的公眾號！

演算法是永無止境的，希望這篇文章能幫你了解一些常見的演算法範式。 相關免費學習推薦：

js影片教學

以上是如何設計演算法？常見的演算法範式介紹的詳細內容。更多資訊請關注PHP中文網其他相關文章！