吳軍《計(jì)算之魂》第六章：分治思想及應(yīng)用-筆記

2023-03-21 18:38 作者:raft0065 0人讀過(guò) | 我要投稿

6.1 分治：從O(N^2)到O(NlgN)

????三部曲：

????1）將一個(gè)復(fù)雜問(wèn)題分解成若干個(gè)簡(jiǎn)單子問(wèn)題，即divide

????2）解決每一個(gè)子問(wèn)題，即conquer，如果子問(wèn)題依然很大，則需要遞歸調(diào)用分治進(jìn)一步分解，直到被分出的子問(wèn)題能夠被直接解決為止

????3）對(duì)子問(wèn)題的結(jié)果進(jìn)行合并，即combine

????1）先分為5組，每組5人，賽5次后，根據(jù)速度分別編號(hào)A1～A5，B1～B5，...，E1～E5，其中A1>A2>...>A5，以此類推

????2）A1，B1，...，E1五個(gè)小組跑最快的人賽一次，不是一般性，設(shè)速度：A1>B1>...>E1

????3）因?yàn)锳1不需要賽了（已經(jīng)第一），D和E組最快的人前面至少有三個(gè)人，也不用賽了直接整組淘汰。同理，可以讓A2，A3，B1，B2，C1再賽一場(chǎng)找亞軍和季軍

????當(dāng)K<<N時(shí)，可以綜合使用【歸并排序】和【堆排序】的思想，時(shí)間復(fù)雜度O((K+N)lgN)，該方法常用作國(guó)際大學(xué)挑選每個(gè)國(guó)家的新生候選人的算法：

????具體為：

????1）將N個(gè)序列從大到小排列

????2）分別在每個(gè)序列中取出最大的那個(gè)數(shù)，建堆（Max Heap）

????3）取出MaxHeap中的最大元素，并根據(jù)該元素所屬的序列號(hào)來(lái)更新該序列的指針下移一個(gè)

6.2 分割算法：快速排序和中值問(wèn)題

????找K個(gè)最大需要建最小堆，逆向思維排除N-K個(gè)，剩下K個(gè)，找K個(gè)最小元素則反之建最大堆

????如果使用堆排，K=N/2，那么時(shí)間復(fù)雜度退化為O(nlgn)，這時(shí)使用快速選擇更好O(n)，詳見《算法導(dǎo)論》，或者使用主定理（Master Theorem）也可：

????和快速排序相比，尋找中值或某一個(gè)K大的數(shù)雖然在代碼上相差無(wú)幾，但實(shí)際上，基于分割原理的中值算法并沒有解決pivot之上或之下的系列數(shù)字的相互關(guān)系，因此要少做很多計(jì)算。并且，從過(guò)程上看，雖然快排和中值算法都要經(jīng)過(guò)很多迭代，但是前者每次都是針對(duì)整個(gè)數(shù)組的元素，后者每次迭代比較的元素則是呈等比數(shù)列遞減的。

????N選K問(wèn)題有很多實(shí)際應(yīng)用，比如在一億個(gè)游戲玩家中尋找100個(gè)最活躍者獎(jiǎng)勵(lì)，或機(jī)器學(xué)習(xí)中，為權(quán)衡計(jì)算和存儲(chǔ)成本，只保留前K個(gè)最有效的特征等。