斯坦福大學(xué)算法分析與設(shè)計(jì)課--分治算法(附小姐姐視頻)
本文預(yù)計(jì)閱讀時(shí)間4分鐘，在讀的過程中你需要帶著以下問題:
分治算法的基本步驟
逆序?qū)τ?jì)數(shù)是如何使用分治算法來解決問題的
為什么MergeSort排序法可以自然的算出逆序?qū)?shù)目
分值策略一般步驟
把輸入劃分成更小的子問題。
遞歸的治理子問題。
把子問題的解決方案組合到一起，形成原始問題的解決方案。
應(yīng)用: 逆序?qū)?shù)目
輸入包含不同整數(shù)的數(shù)組A, 輸出A中逆序?qū)Φ臄?shù)量，逆序是指: 如果 i < j 而 A[i]?> A[j]，那么 (i, j) 就是一組逆序?qū)Α?/span>
比如輸入的數(shù)組是
其中i = 2對(duì)應(yīng)A[2] =3 ，j=4對(duì)應(yīng)A[4]=2，2<4, 但是A[2] > A[4]，所以這是一組逆序?qū)Α?/span>
協(xié)同篩選
為什么要對(duì)數(shù)組的逆序?qū)τ?jì)算？
一個(gè)原因是想要計(jì)算一種數(shù)值相似度，該數(shù)值的相似度用于對(duì)兩個(gè)已排序列表之間的相似度進(jìn)行量化。比如兩個(gè)人都看過10部電影，按照從最喜歡到最不喜歡的順序進(jìn)行排列，那么怎么衡量兩個(gè)人的選擇是相似還是不相似的呢？解決這個(gè)問題的一種量化方法就是通過包含10個(gè)元素的數(shù)組A，A1表示讀者的朋友從電影列表中選擇最喜歡的電影，a2表示他喜歡第二的電影，以此類推，a10表示他最不喜歡的電影，這樣如果讀者最喜歡的電影是星球大戰(zhàn)，而這部電影在讀者的列表中只顯示的第5位，那么a1就等于5，如果兩個(gè)人的排序是相同的，這個(gè)數(shù)組就已經(jīng)排序了，不存在逆序?qū)?，如果這個(gè)數(shù)組包含的逆序?qū)υ蕉?，讀者和朋友之間對(duì)電影評(píng)價(jià)的分歧就越多，對(duì)電影的偏好就不同了。
對(duì)已排序列表進(jìn)行相似性測(cè)量的另一個(gè)原因就是協(xié)同篩選，這是一種任意生成推薦方案的方法，網(wǎng)站就怎么推出關(guān)于產(chǎn)品電影歌曲內(nèi)容的建議呢？在協(xié)同篩選中，其思路就是尋找其他與它相似偏好的用戶，然后推薦他們所喜歡的內(nèi)容。因此協(xié)同篩選需要用戶“相似性”的定義，而計(jì)算逆序?qū)涂梢圆蹲絾栴}的本質(zhì)。
暴力解法
我們首先想到的就是暴力窮舉搜索法，輸入一個(gè)數(shù)組A，里面包含不同的整數(shù)，輸出的是它的逆序?qū)€(gè)數(shù)，以上就是暴力解法的偽代碼。外層循環(huán)i表示從左到右的遍歷數(shù)組A中的元素，內(nèi)層循環(huán)j是沒有與i對(duì)比過的元素，逆序了就累加。它的缺點(diǎn)是時(shí)間復(fù)雜度很高，O(n^2)。
分而治之思想
如果我們用分治算法來算這個(gè)問題的話，第一個(gè)步驟就是把數(shù)組A劃分成更小的子問題，我們把A平均的劃分成兩個(gè)部分，左邊和右邊，這樣數(shù)組規(guī)模就變小了，這樣劃分下就有三種情況:
第1種就是逆序?qū)?i 和 j 都位于數(shù)組的左半部分，就是下標(biāo) i 和 j 是小于等于n/2的
第2種情況是逆序?qū)?i 和 j 位于數(shù)組的右半部分
第3種情況是逆序?qū)?i?位于左半部分 j 位于右半部分，以上是偽代碼。
接下來我們需要解決子問題，對(duì)于情況1，2其實(shí)就是調(diào)用自身的遞歸，所以我們只用實(shí)現(xiàn)第3鐘情況CountSplitInv。
MergeSort思想
在CountInv的偽代碼中，需要實(shí)現(xiàn)CountSplitInv函數(shù)，我們之前講的MergeSort排序算法天然的可以計(jì)算逆序?qū)?shù)目，而它實(shí)現(xiàn)的思路又是兩個(gè)已排序的數(shù)組合并成一個(gè)新數(shù)組，上面的CountInv的情況3實(shí)際就是i在左邊數(shù)組中，j在右邊數(shù)組中，而左右兩邊的數(shù)組沒有排序，所以我們對(duì)他兩排一下序就能引用MergeSort算法。我們稍微的修改一下上面的偽代碼，使得遞歸后除了返回逆序?qū)?shù)目，還要返回排序后的數(shù)組，下面是修改后的偽代碼。
那么以上在處理逆序?qū)?i, j 一個(gè)在左邊一個(gè)在右邊這種情況的時(shí)候，就可以用上之前的MergeSort算法，現(xiàn)在我們來回顧一下。
以上是MergSort的偽代碼，它是輸入已排序的C和D，輸出是排序好的B。i，j分別控制C，D的元素，哪個(gè)元素小就把它加入到B中。那么，這里的C就是原問題中的左半部，D就是原問題的右半部分，當(dāng)C[i] > D[j] 的時(shí)候，說明產(chǎn)生了逆序?qū)Γ鳦又是排序后的，所以i之后的數(shù)字都是大于D[j]的，所以對(duì)于D[j]所帶來的逆序?qū)?shù)目就是C數(shù)組i到最后的元素個(gè)數(shù)，所以，我們可以在排序的基礎(chǔ)上計(jì)算出逆序?qū)€(gè)數(shù)。把這一段話翻譯成偽代碼就是如下。
這樣就完成了分治算法對(duì)于逆序?qū)Φ挠?jì)算。時(shí)間復(fù)雜度是O(nlogn)，比暴力搜索快很多。文章開頭的問題你想通了嗎？ps:開頭的視頻，是美女小姐姐錄制的哦，記得拉上去看看！
有熱門推薦?