javascript常見的算法范式有哪些

這篇文章將為大家詳細(xì)講解有關(guān)javascript常見的算法范式有哪些，小編覺得挺實(shí)用的，因此分享給大家做個(gè)參考，希望大家閱讀完這篇文章后可以有所收獲。

首先明確三個(gè)概念：

算法： 按步驟解決問題的過(guò)程。

范式： 思考問題的模式。

算法范式： 為問題構(gòu)建高效解決方案的常規(guī)方法。

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

• 分治算法
• 動(dòng)態(tài)規(guī)劃
• 貪婪算法
• 回溯算法

分治法

在排序算法中，合并和快速排序這兩種算法的共同點(diǎn)就是分而治之的算法。

分而治之是一種常見的算法設(shè)計(jì)，它的思路是把問題分解為與原始問題相似的較小子問題。通常以遞歸方式解決子問題，并結(jié)合子問題的解決方案來(lái)解決原始問題。

分治法的邏輯可以分為三個(gè)步驟：

1. 將原始問題劃分為較小的子問題。
2. 通過(guò)遞歸解決子問題，解決完畢之后返回子問題的解決方案。
3. 將子問題的解決方案合并為原始問題的解決方案。

分治法的例子：二叉搜索

下面是用分治實(shí)現(xiàn)的二叉搜索。

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);
}

請(qǐng)注意，上面的 binarySearch 函數(shù)是供他人調(diào)用的，而 binarySearchRecursive 是實(shí)現(xiàn)分治法的地方。

動(dòng)態(tài)規(guī)劃法

動(dòng)態(tài)規(guī)劃是一種優(yōu)化技術(shù)，用于通過(guò)把復(fù)雜問題分解為較小的子問題來(lái)解決?？瓷先ズ芟袷欠种畏ǎ珓?dòng)態(tài)規(guī)劃不是把問題分解為獨(dú)立的子問題然后再組合在一起，而是只把問題分解為獨(dú)立的子問題。

算法邏輯分為三個(gè)步驟：

1. 定義子問題。
2. 重復(fù)解決子問題。
3. 識(shí)別并解決基本問題。

動(dòng)態(tài)規(guī)劃案例：最小硬幣找零問題

這是一個(gè)名為為硬幣找零問題的常見面試題。硬幣找零問題是給定找零的金額，找出可以用多少特定數(shù)量的硬幣來(lái)找零的方式。最小硬幣找零問題只是找到使用給定面額的錢所需的最少硬幣數(shù)量。例如，如果需要找零 3 毛 7 分，則可以使用 1 個(gè) 2 分，1個(gè) 5 分，1 個(gè) 1 毛錢和1個(gè) 2 毛錢。

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);
}

在上面的代碼中，參數(shù) coins 表示面額（在人民幣中為 [1, 2, 5, 10, 20, 50]）。為了防止重復(fù)計(jì)算，用到了一個(gè) cache 。 makeChange 函數(shù)是遞歸實(shí)現(xiàn)的，它是一個(gè)內(nèi)部函數(shù)，可以訪問 cache。

console.log(minCoinChange([1, 2, 5 10, 20], 37)); // => [2, 5, 10, 20]
console.log(minCoinChange([1, 3, 4], 6)) // => [3, 3]

貪心算法

貪心算法與當(dāng)前的最優(yōu)解決方案相關(guān)，并試圖找到一個(gè)全局的最佳方案。與動(dòng)態(tài)規(guī)劃不同，它不考慮全局。貪心算法傾向于簡(jiǎn)單直觀，但可能不是整體最優(yōu)的解決方案。

貪心算法案例：最小硬幣找零問題

上面用動(dòng)態(tài)規(guī)劃解決的硬幣問題也可以用貪心算法解決。這個(gè)解決方案的是否能得到最優(yōu)解取決于所采用的面額。

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;
}

可以看到，貪心算法比動(dòng)態(tài)規(guī)劃的方案要簡(jiǎn)單得多。下面看一下同樣的求解案例，來(lái)了解兩者之間的區(qū)別：

console.log(minCoinChange([1, 2, 5 10, 20], 37)); // => [2, 5, 10, 20]
console.log(minCoinChange([1, 3, 4], 6)) // => [4, 1, 1]

貪心算法給出了第一個(gè)問題的最優(yōu)解，但第二個(gè)并不是最優(yōu)解（應(yīng)該是 [3，3]）。

貪心算法比動(dòng)態(tài)規(guī)劃算法要簡(jiǎn)單而且更快，但是得到的有可能不是最優(yōu)解。

回溯算法

回溯算法非常適合逐步查找和構(gòu)建解決方案。

1. 嘗試以一種方式解決問題。
2. 如果它不起作用，就回溯并重復(fù)步驟 1，直到找到合適的解決方案為止。

對(duì)于回溯算法，我會(huì)另寫一篇文章來(lái)介紹更復(fù)雜的算法。究竟寫什么我還沒想好，也許是寫一個(gè)對(duì)數(shù)獨(dú)求解的程序，如果你對(duì)這個(gè)感興趣，請(qǐng)關(guān)注我的公眾號(hào)！

算法是永無(wú)止境的，希望本文能幫你了解一些常見的算法范式。

關(guān)于javascript常見的算法范式有哪些就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，可以學(xué)到更多知識(shí)。如果覺得文章不錯(cuò)，可以把它分享出去讓更多的人看到。