分治法的思想與經典題目

分治法簡介

分治法,即「分而治之」,就是將原問題分解為幾個規模較小但是類似於原問題的子問題,遞歸求解這些子問題, 然後再合併這些問題的解來建立原問題的解。

分治法主定理

分治法通常遵守一種通用模式:在解決規模為n的問題時,總是先遞歸地求解a個規模為n/b的子問題,然後在O\left ( n^{d} \right )時間內將子問題的解合併起來。分治演算法的運行時間為:

T\left ( n \right ) = a T \left ( \left \lceil \frac{n}{b} \right \rceil \right ) + O\left ( n^{d} \right )

分治演算法的時間複雜度

一般的,當a,b,d > 0且下式

T\left ( n \right ) = a T \left ( \left \lceil \frac{n}{b} \right \rceil \right ) + O\left ( n^{d} \right )

成立時,有:

T\left ( n \right ) = \begin{cases} O \left ( n^{d} \right ) & \text{ } d>\log_{b}{a} \\ O \left ( n^{d} \log_{2}{n} \right ) & \text{ } d=\log_{b}{a} \\ O \left ( n^{\log_{b}{a}} \right ) & \text{ } d<\log_{b}{a} \end{cases}

分治法的基本步驟

  • 分解:分解原問題為若干子問題,這些子問題是原問題的規模最小的實例;

  • 解決:解決這些子問題,遞歸地求解這些子問題。當子問題的規模足夠小,就可以直接求解;

  • 合併:合併這些子問題的解成原問題的解。

分治法的使用條件

  • 該問題的規模縮小到一定的程度就可以容易地解決;

    • 隨著問題規模的減少,問題自然會容易解決。

  • 該問題可以分解為若干個規模較小的相同問題;

    • 分治法的前提。

  • 利用該問題分解出的子問題的解可以合併為該問題的解;

    • 分治法的前提。

  • 該問題所分解出的各個子問題是相互獨立的,即子問題之間不包含公共的子子問題。(非必需)

    • 對於存在公共子問題的情況,使用分治演算法會存在重複計算的問題,使用動態規劃較為合適。

分治法的經典題目

50. Pow(x, n) 

難度 中等

題目:實現 pow(x, n) ,即計算 x 的 n 次冪函數。

思路:

  • 當我們要計算x^{n}時,我們可以先遞歸地計算出y=x^{\left \lfloor \frac{n}{2} \right \rfloor },其中\left \lfloor a \right \rfloor表示對 aa 進行下取整;

  • 根據遞歸計算的結果,如果 n 為偶數,那麼x^{n}=y^{2};如果 n 為奇數,那麼x^{n}=y^{2} * x

  • 遞歸的邊界為 n=0,任意數的 0 次方均為 1。

class Solution:
    def myPow(self, x: float, n: int) -> float:
        """遞歸"""
        # 若x為0,直接返回0.0
        if not x:
            return 0.0
 
        def inner(m):
            # 規模最小的子問題的解
            if m == 0:
                return 1.
 
            y = inner(m // 2)   # 分解問題
 
            # 合併子問題的解,冪為奇數或偶數時分開處理
            return y * y if m % 2 == 0 else y * y * x
 
        return inner(n) if n >= 0 else 1. / inner(-n)   # 處理冪為負數時的情況

思路:

  • 通過循環x=x^{2}操作,每次把冪從 n 降至n//2,直至將冪降為 0 ;

  • 設 res=1 ,則初始狀態x^{n}=x^{n}\times res。在循環二分時,每當 n 為奇數時,將多出的一項 x 乘入 res ,則最終可化至x^{n}=x^{0}\times res=res,返回 res 即可。

class Solution:
    def myPow(self, x: float, n: int) -> float:
        """迭代"""
        # 若x為0,直接返回0.0
        if not x:
            return 0.0
 
        # 處理冪為負數時的情況
        if n < 0:
            x = 1 / x
            n = -n
 
        res = 1
        while n:
            # 處理冪為奇數的情況
            if n & 1:
                res *= x    # 合併子問題的解
            x *= x
            n >>= 1     # 分解問題
 
        return res

53. 最大子序和

難度 簡單

題目:給定一個整數數組 nums,找到一個具有最大和的連續子數組(子數組最少包含一個元素),返回其最大和。

思路:按照數組中心將數組劃分為左右兩部分,最大子序要麼在左半部分,要麼在右半部分,要麼跨中心,這三種情況。跨中心的情況,再分治成中心點左側和右側的最大子序和問題。

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
 
        if n == 1:
            # 規模最小的子問題的解
            return nums[0]
        else:
            # 分解問題
            max_left = self.maxSubArray(nums[: n // 2])     # 求左半邊最大子序和
            max_right = self.maxSubArray(nums[n // 2:])     # 求右半邊最大子序和
 
        # 計算中間的最大子序和
        # 從右到左計算左邊的最大子序和
        max_l = nums[n // 2 - 1]
        tmp = 0
        for i in range(n // 2 - 1, -1, -1):
            tmp += nums[i]
            max_l = max(tmp, max_l)
 
        # 從左到右計算右邊的最大子序和
        max_r = nums[n // 2]
        tmp = 0
        for i in range(n // 2, n):
            tmp += nums[i]
            max_r = max(tmp, max_r)
 
        # 返回三個中的最大值
        return max(max_left, max_right, max_l + max_r)

169. 多數元素

難度 簡單

題目:給定一個大小為 n 的數組,找到其中的多數元素。多數元素是指在數組中出現次數大於 ⌊ n/2 ⌋ 的元素。你可以假設數組是非空的,並且給定的數組總是存在多數元素。

思路:如果數 a 是數組 nums 的眾數,如果我們將 nums 分成兩部分,那麼 a 必定是其中一部分的眾數。這樣一來,我們就可以使用分治法解決這個問題:將數組分成左右兩部分,分別求出左半部分的眾數 a1 以及右半部分的眾數 a2,隨後在 a1 和 a2 中選出正確的眾數。

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        def inner(head, tail):
            # 規模最小的子問題的解
            if head == tail:
                return nums[head]
 
            # 分解問題
            mid = (tail - head) // 2 + head
            left = inner(head, mid)
            right = inner(mid+1, tail)
 
            if left == right:
                return left
 
            left_count = sum([1 for i in nums[head: tail+1] if i == left])
            right_count = sum([1 for i in nums[head: tail+1] if i == right])
 
            return left if left_count > right_count else right  # 合併子問題的解
 
        return inner(0, len(nums) - 1)