分治算法介紹

今天我們聊一聊計(jì)算機(jī)中非常重要和常用的一種算法：分治算法。它在計(jì)算機(jī)領(lǐng)域應(yīng)用廣泛，幾乎無(wú)處不在。不僅計(jì)算機(jī)領(lǐng)域，在信號(hào)處理領(lǐng)域，分而治之也是十分常見的一種信號(hào)處理方法。著名快速傅里葉變換算法 (FFT) 正是使用了分而治之的思路，才使得數(shù)字信號(hào)處理算能廣泛使用，這也才造就了我們今天豐富多彩的生活。

1. 分治算法思想

分而治之是計(jì)算機(jī)領(lǐng)域中非常重要的一種思想：即將大規(guī)模問(wèn)題每次通過(guò)分解成小問(wèn)題進(jìn)行處理，在處理完小問(wèn)題之后再將結(jié)果合并成大問(wèn)題的最終結(jié)果。

2. 舉例說(shuō)明分治算法的典型應(yīng)用

非常典型的一個(gè)示例是排序算法中的歸并排序。假設(shè)我們要排序 8 個(gè)數(shù)，我們首先將 8 個(gè)數(shù)的列表分解成兩個(gè) 4 個(gè)數(shù)的列表，一直劃分下去直到列表中最多只有 2 個(gè)元素。接下來(lái)對(duì)所有的 2 個(gè)或者 1 個(gè)元素的列表進(jìn)行排序，然后再兩兩合并，直到最后合并成最終長(zhǎng)度為 8 的列表，則排序結(jié)束。其算法示意圖如下所示：

可以看到：歸并排序中的一個(gè)核心步驟是對(duì)兩個(gè)有序數(shù)組的合并過(guò)程，對(duì)此使用的合并算法過(guò)程如下圖所示：

3. 分治算法的 Python 代碼實(shí)現(xiàn)

有了上面的算法過(guò)程，我們就可以寫出合并兩個(gè)有序列表的代碼，如下：

def merge_sorted_list(nums1, nums2):
    """
    合并有序列表
    """
    nums = [0] * (len(nums1) + len(nums2))
    id, id1, id2 = 0, 0, 0
    # 循環(huán)條件，當(dāng)有一個(gè)等于數(shù)組長(zhǎng)度時(shí)，終止
    while id1 < len(nums1) and id2 < len(nums2):
        # 對(duì)應(yīng)著上圖中第三個(gè)操作，多加了邊界操作
        while id1 < len(nums1) and id2 < len(nums2) and nums1[id1] <= nums2[id2]:
            nums[id] = nums1[id1]
            id += 1
            id1 += 1
        # 對(duì)應(yīng)著上圖第二個(gè)部分操作，多加了邊界操作
        while id1 < len(nums1) and id2 < len(nums2) and nums2[id2] < nums1[id1]:
            nums[id] = nums2[id2]
            id += 1
            id2 += 1

    # 對(duì)應(yīng)于圖片的最后部分，如果一個(gè)數(shù)組先走完，另一個(gè)數(shù)組剩余部分直接添加到新數(shù)組的最后
    if id1 != len(nums1):
        nums[id:] = nums1[id1:] 

    if id2 != len(nums2):
        nums[id:] = nums2[id2:] 

    return nums

接下來(lái)從分解到合并這個(gè)過(guò)程是不是特別像遞歸？看看遞歸三要素應(yīng)該怎么做，第一是終止條件，很明顯在列表長(zhǎng)度為 1 或者 2 時(shí)終止；第二是方法的返回值，可以是列表頭，表示得到新的排序的列表；第三是遞推公式，即將已經(jīng)排好序的結(jié)果合并成完整的排序結(jié)果，用的正是上面的合并方法，這樣我們就可以寫出如下歸并排序的代碼：

def merge_sort(nums):
    """
    遞歸終止條件
    """
    if len(nums) == 1:
        return nums
    if len(nums) == 2:
        if nums[0] > nums[1]:
            nums[0], nums[1] = nums[1], nums[0]
        return nums
    
    # 遞歸公式，將列表平均分成兩份，然后遞歸排序下去
    half = len(nums) // 2
    nums1 = merge_sort(nums[:half])
    nums2 = merge_sort(nums[half:])
    # 調(diào)用合并操作，得到最終結(jié)果
    return merge_sorted_list(nums1, nums2)

從上面的排序算法示例中我們可以看到典型分治算法的解題步驟如下：

• 分解：要解決的問(wèn)題劃分成若干規(guī)模較小的同類問(wèn)題；
• 求解：當(dāng)子問(wèn)題劃分得足夠小時(shí)，可以采用已有或者簡(jiǎn)單的算法解決；
• 合并：再得到每個(gè)子問(wèn)題的解后，還需要將這些結(jié)果合并成最后大問(wèn)題的結(jié)果，這才是最終答案。

4. 另一個(gè)分而治之的應(yīng)用介紹

另一個(gè)分治算法的典型應(yīng)用是大整數(shù)相乘問(wèn)題。對(duì)于兩個(gè)以字符串形式表示的長(zhǎng)整數(shù)，計(jì)算其相乘結(jié)果。關(guān)于分治法比較核心的一個(gè)問(wèn)題就是，找到如何將子問(wèn)題的解合并成父問(wèn)題的解。我們簡(jiǎn)單描述一下這個(gè)基于分治思想的大數(shù)乘法算法，又叫 Karatsuba 算法。

假設(shè) x 和 y 是兩個(gè)要做乘法的十進(jìn)制大數(shù)，并且位數(shù)分別為 m 和 n。若將 x 和 y 分別均分成兩部分，則 x 和 y 可以表示如下：
$x = a*10^{\frac{m}{2}} + b$
$y = c*10^{\frac{n}{2}} + d$
此時(shí)有：
$x*y=(a*10^{\frac{m}{2}} + b)(c*10^{\frac{n}{2}} + d)=ac*10^{\frac{m+n}{2}}+bc*10^{\frac{n}{2}}+ad*10^{\frac{m}{2}}+bd$
這樣大整數(shù)乘法就被分解成 4 個(gè)長(zhǎng)度減半的整數(shù)的乘法。如此執(zhí)行下去，直到執(zhí)行的乘法的兩數(shù)足夠小時(shí)，然后計(jì)算反推最終結(jié)果。根據(jù)上面的執(zhí)行思路，我們開始一步一步得到大整數(shù)相乘的分治代碼。

首先處理初始以及最后分治的終止條件：如果 s1 或者 s2 中有一個(gè)為空串，那么相乘結(jié)果為 '0‘，注意輸出字符串；此外，分解到最后 s1 和 s2 字符串的長(zhǎng)度均為1 時(shí)，我們可以直接將兩個(gè)字符串強(qiáng)裝成數(shù)字然后進(jìn)行相乘，最后返回的結(jié)果也要再轉(zhuǎn)成字符串：

if not s1 or not s2:
    # 有一個(gè)為空，則結(jié)果為0
    return '0'
elif len(s1) == 1 and len(s2) == 1:
    # 終止條件
    return str(int(s1) * int(s2))

接下來(lái)開始對(duì)字符串 s1 和 s2 進(jìn)行分治求解：

# 其余情況
l1 = len(s1) // 2
l2 = len(s2) // 2

# 將s1分成兩部分
a = s1[:l1] 
b = s1[l1:]
# 將s2分成兩部分
c = s2[:l2]
d = s2[l2:]

接下來(lái)我們分別得到了4個(gè)子串：a、b、c、d。按照前面的公式，我們分別要計(jì)算 ac、bc、ad 和 bd 的值。這些值可以使用遞歸方法得到，要注意相乘結(jié)果的10次冪需要保留，以便后續(xù)能合成最終問(wèn)題的解。

mi = len(b) # 對(duì)于a的10次冪
ni = len(d) # 對(duì)于c的10次冪
# 分別計(jì)算ac, ad, bc, bd，分別補(bǔ)上相應(yīng)的冪次，使用分治計(jì)算
x1 = bigDataMultiple(a, c) + '0' * (mi + ni)
x2 = bigDataMultiple(a, d) + '0' * mi
x3 = bigDataMultiple(b, c) + '0' * ni 
x4 = bigDataMultiple(b, d)

最后是計(jì)算 x1+x2+x3+x4 的值便可得到原大問(wèn)題的解，由于 x1~x4 均為字符串，我們按照字符串上每位數(shù)字相加來(lái)進(jìn)行。首先需要將所有字符串的長(zhǎng)度統(tǒng)一，對(duì)于短字符串需要將前面補(bǔ)零：

max_len = max(len(x1), len(x2), len(x3), len(x4))
x1 = '0' * (max_len - len(x1)) + x1
x2 = '0' * (max_len - len(x2)) + x2
x3 = '0' * (max_len - len(x3)) + x3
x4 = '0' * (max_len - len(x4)) + x4

接著從字符串最后一位開始，計(jì)算每位上的值，注意進(jìn)位問(wèn)題即可：

res = ''
c = 0
for i in range(max_len - 1, -1, -1):
    s = int(x1[i]) + int(x2[i]) + int(x3[i]) + int(x4[i]) + c
    res = str(s % 10) + res
    c = s // 10
# 注意，如果循環(huán)完后進(jìn)位>0，需要補(bǔ)上進(jìn)位值
if c > 0:
    res = str(c) + res

然而，通過(guò)提交代碼發(fā)現(xiàn)有時(shí)候在合成最終結(jié)果時(shí)，字符串前面會(huì)出現(xiàn) ‘0’。因此下面的代碼就是找到前面非 ‘0’ 開頭字符的位置：

# 去掉res最前面的'0'
k = 0
while res and k < len(res) and res[k] == '0':
    k += 1

最后得到大整數(shù)相乘的最終結(jié)果為：res[k:]。

綜合前面的分析與討論，得到完成的處理大整數(shù)相乘問(wèn)題的 Python 實(shí)現(xiàn)如下：

def bigDataMultiple(s1, s2):
    """
    計(jì)算 s1 * s2，返回大整數(shù)相乘結(jié)果
    """
    if not s1 or not s2:
        # 有一個(gè)為空，則結(jié)果為0
        return '0'
    elif len(s1) == 1 and len(s2) == 1:
        # 終止條件
        return str(int(s1) * int(s2))

    # 其余情況
    l1 = len(s1) // 2
    l2 = len(s2) // 2

    # 將s1分成兩部分
    a = s1[:l1] 
    b = s1[l1:]
    # 將s2分成兩部分
    c = s2[:l2]
    d = s2[l2:]
    
    mi = len(b) # 對(duì)于a的10次冪
    ni = len(d) # 對(duì)于c的10次冪
    # 分別計(jì)算ac, ad, bc, bd，分別補(bǔ)上相應(yīng)的冪次，使用分治計(jì)算
    x1 = bigDataMultiple(a, c) + '0' * (mi + ni)
    x2 = bigDataMultiple(a, d) + '0' * mi
    x3 = bigDataMultiple(b, c) + '0' * ni 
    x4 = bigDataMultiple(b, d)

    # 將計(jì)算的結(jié)果根據(jù)最長(zhǎng)的補(bǔ)零，方便后面直接相加計(jì)算
    max_len = max(len(x1), len(x2), len(x3), len(x4))
    x1 = '0' * (max_len - len(x1)) + x1
    x2 = '0' * (max_len - len(x2)) + x2
    x3 = '0' * (max_len - len(x3)) + x3
    x4 = '0' * (max_len - len(x4)) + x4
   
    # 計(jì)算x1+x2+x3+x4的值，也就是原問(wèn)題的解
    res = ''
    c = 0
    for i in range(max_len - 1, -1, -1):
        s = int(x1[i]) + int(x2[i]) + int(x3[i]) + int(x4[i]) + c
        res = str(s % 10) + res
        c = s // 10
    # 注意，如果循環(huán)完后進(jìn)位>0，需要補(bǔ)上進(jìn)位值
    if c > 0:
        res = str(c) + res
        
    # 去掉res最前面的'0'
    k = 0
    while res and k < len(res) and res[k] == '0':
        k += 1
    return res[k:]

這道題是?？途W(wǎng)上的原題，我實(shí)現(xiàn)的分治算法略微復(fù)雜，大家可以參考上面的一些題解，有非常精簡(jiǎn)和高效的實(shí)現(xiàn)。多參考優(yōu)秀的代碼對(duì)我們提升自己編程能力也是有莫大好處的。

5. 分治法的時(shí)間復(fù)雜度分析

分治法的時(shí)間復(fù)雜度可以這樣來(lái)分析，假設(shè)對(duì)于規(guī)模為 n 的問(wèn)題，其直接計(jì)算的復(fù)雜度為 $O(n^2)$。那么我們看一下分解成 2 個(gè)子問(wèn)題后其復(fù)雜度如何？我們以前面的歸并排序的為例，如果是采用前面的選擇排序、冒泡排序，算法的復(fù)雜度為 $O(n^2)$，我們將其分解成兩個(gè) $\frac{n}{2}$ 長(zhǎng)度的列表進(jìn)行排序后再合并，這樣一次分解的時(shí)間復(fù)雜度為：
$(\frac{n}{2})^2+(\frac{n}{2})^2+n=\frac{n^2}{2}+n$
注意：后面的 n 為合并方法的時(shí)間復(fù)雜度。如果問(wèn)題規(guī)模 n 非常大，此時(shí)一次分解再合并后的時(shí)間復(fù)雜度相比原算法少了一半，如果我們?cè)俅畏纸鈫?wèn)題規(guī)模呢？
$(\frac{n}{4})^2+(\frac{n}{4})^2+\frac{n}{2}=\frac{n^2}{8}+\frac{n}{2}$
可以看到再次減少大約一半的計(jì)算量！?。∪绻瓎?wèn)題的復(fù)雜度是 $O(n^3)$ 甚至 $O(2^n)$ ，那么使用分治算法能明顯改進(jìn)原算法性能，當(dāng)前前提是該算法能進(jìn)行分治求解。對(duì)于前面歸并排序問(wèn)題，其平均的時(shí)間復(fù)雜度最終可以達(dá)到 $O(n*logn)$。

6. 小結(jié)

本小節(jié)我們使用兩個(gè)典型的例子對(duì)分治算法的原理以及算法實(shí)現(xiàn)步驟進(jìn)行了相應(yīng)的說(shuō)明，通過(guò)這兩個(gè)簡(jiǎn)單的例子我們能體會(huì)分治算法的特點(diǎn)：簡(jiǎn)單高效。接下來(lái)我們會(huì)用更多 leetcode 習(xí)題來(lái)幫助我們鞏固這一節(jié)所學(xué)的算法。