文章結(jié)構(gòu)
- 如何理解分治算法
- 分治算法應(yīng)用舉例
1. 如何理解分治算法
1.1 分治算法的核心思想
分治算法的核心思想簡單來說就四個字礼华，分而治之咐鹤。也就是將一個大的問題分解成多個規(guī)模較小但是結(jié)構(gòu)相似的子問題，遞歸的解決這些子問題圣絮，然后合并這些子問題的解來得到原問題的解祈惶。
1.2 分治算法的遞歸實現(xiàn)思路
分治算法一般比較適合用遞歸來實現(xiàn)。分治算法的遞歸實現(xiàn)扮匠，每一層都涉及這樣三個操作：
- 分解：將原問題分解成一些列的子問題
- 解決：遞歸的求解各個子問題捧请，若子問題足夠小，則直接求解
- 合并：將子問題的解合并成原問題的解
1.3 什么樣的問題適合用分治思想來解決
- 一個問題能夠分解成多個結(jié)構(gòu)相似棒搜、規(guī)模較小的子問題
- 子問題要能夠獨立求解疹蛉，彼此之間沒有相關(guān)性
- 問題分解要有終止條件，也就是當(dāng)問題足夠小的時候力麸，可以直接解決
- 合并子問題的解的復(fù)雜度不能太高可款，否則就起不到減少算法總體復(fù)雜度的效果
2. 分治算法應(yīng)用舉例
2.1 歸并排序
歸并排序就是典型的分治思想應(yīng)用育韩。歸并排序的思想就是：先將要排序的數(shù)據(jù)分成兩個部分，先對這兩個部分進(jìn)行排序筑舅，然后再將排好序的兩個有序序列進(jìn)行合并座慰。
2.2 海量數(shù)據(jù)排序
假設(shè)有10GB的訂單文件需要按照金額進(jìn)行排序陨舱，而能夠使用的及其內(nèi)存只有2翠拣、3個GB，如何進(jìn)行排序呢游盲？
可以先將這些數(shù)據(jù)分成多份误墓，然后將每一份數(shù)據(jù)單獨調(diào)入內(nèi)存進(jìn)行排序，待每份數(shù)據(jù)都排好序之后益缎。在將這些數(shù)據(jù)合并成一個有序序列谜慌。
