算法設(shè)計(jì)技巧: 分治法 (Divide & Conquer)

分治法是一種非常通用的算法設(shè)計(jì)技巧. 在很多實(shí)際問(wèn)題中, 相比直接求解, 分治法往往能顯著降低算法的計(jì)算復(fù)雜度. 常見(jiàn)的可以用分治法求解的問(wèn)題有: 排序, 矩陣乘法, 整數(shù)乘法, 離散傅里葉變換等. 分治法的一般思路如下:

[Divide] 把原問(wèn)題拆分成同類型的子問(wèn)題.
[Conquer] 用遞歸的方式求解子問(wèn)題.
[Combine] 根據(jù)子問(wèn)題的解構(gòu)造原問(wèn)題的解.

分治法最關(guān)鍵的步驟是如何 低成本地 利用子問(wèn)題的解構(gòu)來(lái)造原問(wèn)題的解. 它包含兩個(gè)方面: 1. 可行性, 即, 可以用子問(wèn)題的解來(lái)構(gòu)造原問(wèn)題的解; 2. 高效性, 即構(gòu)造原問(wèn)題解的時(shí)間復(fù)雜度較低. 換句話說(shuō), 分治法需要比直接求解效率高. 分治法一般是通過(guò)遞歸求解子問(wèn)題, 其時(shí)間復(fù)雜度的分析需要用到如下定理.

Master Theorem^[1]. 考慮遞歸式 $T(n) = a T(n/b) + f(n)$ . 當(dāng) $f(n) \in \Theta(n^d)$ , $d\geq 0$ 時(shí), 我們有
$\begin{aligned} T(n) = \begin{cases} \Theta(n^d) & \text{ if } a < b^r1xr31n \\ \Theta(n^d \log n) & \text{ if } a = b^d \\ \Theta(n^{\log_b a}) & \text{ if } a > b^d \end{cases} \end{aligned}$

Counting Inversions^[2]

在推薦場(chǎng)景中, 一個(gè)常用的方法是協(xié)同過(guò)濾(Collaborative Filtering), 即為相似的用戶推薦它們共同喜歡的事物. 以推薦歌曲為例, 我們把用戶 $A$ 和 $B$ 對(duì)歌曲的偏好分別進(jìn)行排序, 然后計(jì)算有多少首歌在 $A$ 和 $B$ 的排序是"不同的". 最后根據(jù)這種不同來(lái)定義用戶 $A$ 和 $B$ 的相似性, 從而進(jìn)行歌曲推薦. 具體來(lái)說(shuō), 對(duì)用戶 $A$ 對(duì)歌曲的偏好按 $1, 2, \ldots, n$ 編號(hào). 用戶 $B$ 對(duì)歌曲的偏好可以表示為
$a_1 < a_2 < \ldots < a_n.$

對(duì)任意的 $i<j$ , 如果 $a_i > a_j$ , 我們稱 $a_i$ 和 $a_j$ 稱為 反序(inversion). 換句話說(shuō), 用戶A把歌曲 $i$ 排在歌曲 $j$ 的前面, 但是用戶B把歌曲 $j$ 排在了歌曲 $i$ 的前面.

問(wèn)題描述

給定無(wú)重復(fù)數(shù)字的整數(shù)序列 $a_1, a_2, \ldots, a_n$ , 計(jì)算其反序的數(shù)量.

算法設(shè)計(jì)

直接求解的思路是考慮所有的二元組 $(a_i, a_j)$ 并判斷它們是否反序. 這個(gè)算法的時(shí)間復(fù)雜度是 $O(n^2)$ . 下面我們用分治法來(lái)降低計(jì)算復(fù)雜度.

注意到這個(gè)問(wèn)題實(shí)際上與排序非常類似. 通過(guò)對(duì)序列進(jìn)行排序的同時(shí)記錄不滿足"順序"的二元組數(shù)量, 即反序的數(shù)量. 令 $k=\lfloor n/2 \rfloor$ . 把序列分成兩部分:

$\begin{aligned} & \text{left} = \{a_1, a_2, \ldots, a_k\} \\ & \text{right} = \{a_{k+1}, a_{k+2}, \ldots, a_n\}. \end{aligned}$

用遞歸的方式對(duì)left和right進(jìn)行排序, 同時(shí)計(jì)算left和right中的反序數(shù)量. 當(dāng)序列的長(zhǎng)度為1時(shí), 返回0. 下一步是合并子問(wèn)題的解. 注意到left和right已經(jīng)是按照從小到大的順序進(jìn)行排列. 比較left和right的第一個(gè)元素并把較小的元素添加到結(jié)果中直到left或right為空, 最后再把剩余的序列添加到結(jié)果集. 在比較過(guò)程中我們需要記錄反序的數(shù)量. 當(dāng)right中的元素小于left中的元素時(shí), 反序的增量為"left中剩余元素的數(shù)量". 最終的結(jié)果包含三部分之和: left中反序的數(shù)量, rihgt中反序的數(shù)量和合并時(shí)反序的數(shù)量.

Python實(shí)現(xiàn)

整體的計(jì)算過(guò)程.

def sort_and_count(x):
    if len(x) == 1:
        return x, 0
    k = len(x) // 2
    left, count_left = sort_and_count(x[0: k])
    right, count_right = sort_and_count(x[k:])
    # 把子問(wèn)題的解拼接成原問(wèn)題的解
    combined, count = merge_and_count(left, right)
    return combined, count + count_left + count_right

歸并過(guò)程.

def merge_and_count(left, right):
    """ 把left和right合并且計(jì)算inversion的數(shù)量
    注意: left和right已經(jīng)排好序
    """
    combined = []
    count = 0
    while len(left) and len(right):
        if left[0] > right[0]:  # 反序(左邊的編號(hào)小于右邊的編號(hào)是正序)
            combined.append(right.pop(0))
            count += len(left)
        else:  # 正序
            combined.append(left.pop(0))
    return combined + left + right, count

完整代碼

計(jì)算復(fù)雜度

容易分析歸并過(guò)程的時(shí)間復(fù)雜度是 $O(n)$ . 令 $T(n)$ 代表算法的時(shí)間復(fù)雜度, 我們有

$T(n) \leq 2T(n/2) + cn, \quad c \text{ is constant}.$

根據(jù)Master Theorem, 我們得到 $T(n) = \Theta(n\log n)$ .

Closest Pair^[2]

Closest Pair是計(jì)算幾何里的一個(gè)基本問(wèn)題: 給定二維平面上的 $n$ 個(gè)點(diǎn), 找到距離最近的兩個(gè)點(diǎn). 通過(guò)計(jì)算任意兩點(diǎn)的距離可以在 $O(n^2)$ 找到距離最近的兩點(diǎn). 下面利用分治法可以把時(shí)間復(fù)雜度降低到 $O(n\log n)$ .

算法設(shè)計(jì)

如果所有點(diǎn)是一維的, 我們可以把它們排序, 然后計(jì)算所有相鄰兩點(diǎn)的最小距離. 排序耗時(shí) $O(n\log n)$ , 計(jì)算相鄰點(diǎn)的最小距離耗時(shí) $O(n)$ , 因此算法的時(shí)間復(fù)雜度為 $O(n\log n)$ . 在二維情形, 我們的思路是類似的:

沿著 $x$ 軸方向?qū)c(diǎn)集 $P$ 進(jìn)行排序得到 $P_x = \{(x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n) \}$ .
把 $P_x$ 按與 $x$ 軸垂的方向均分成兩部分 $Q$ 和 $R$ :
$\begin{aligned} & Q = \{(x_1, y_1), (x_2, y_2), \ldots, (x_{k}, y_{k})\}, \quad k=\lfloor n/2\rfloor \\ & R = \{(x_{k+1}, y_{k+1}), (x_{k+2}, y_{k+2}), \ldots, (x_n, y_n)\}. \end{aligned}$
遞歸地求解 $Q$ 和 $R$ 中的closest pair(如下圖所示).

image
根據(jù) $Q$ 和 $R$ 的計(jì)算結(jié)果構(gòu)造原問(wèn)題的解(見(jiàn)下文).

合并(Combine)

設(shè) $(q_0, q_1)$ , $(r_0, r_1)$ 分別是 $Q$ 和 $R$ 中的closest pair. 如果 $P$ 的closest pair在 $P$ 或 $Q$ 中, 我們只需要從 $(q_0,q_1)$ 和 $(r_0, r_1)$ 選擇距離小的pair作為結(jié)果輸出. 否則 $P$ 的closest pair其中一點(diǎn)在 $Q$ 中, 另一點(diǎn)在 $R$ 中, 這時(shí)我們需要比較 $Q$ 和 $R$ 中的點(diǎn). 這樣一來(lái), 合并的時(shí)間復(fù)雜度為 $O(n^2)$ ! 接下來(lái)我們要把合并的時(shí)間復(fù)雜度降低為 $O(n)$ .

令 $\delta = \min \{d(q_0, q_1), d(r_0, r_1)\}$ , 其中 $d(x,y)$ 代表 $x$ , $y$ 兩點(diǎn)之間的距離. 設(shè) $L = \{x = x_0 \}$ 代表 $Q$ 和 $R$ 的分割線. 如果存在 $q\in Q$ , $r\in R$ 使得 $d(p,r) < \delta$ , 那么 $q$ 和 $r$ 在 $x$ 軸方向距離 $L$ 一定不超過(guò) $\delta$ . 令 $S = \{(x,y)\in P, \text{s.t. } |x-x_0| < \delta \}$ , 因此 $q, r \in S$ . 如下圖所示, $S$ 中的點(diǎn)在藍(lán)色虛線之間.
[圖片上傳失敗...(image-facf8c-1586865336187)]
把 $S$ 中的點(diǎn)按 $y$ 軸從小到大排序, 得到集合 $S_y = \{s_1, s_2 \ldots \}$ , 其中 $s_i$ 是一個(gè)二元組(代表它在平面中的位置). 我們有如下定理(稍后給出證明):

定理如果存在 $s_i, s_j \in S_y$ 滿足 $d(s_i,s_j) < \delta$ , 那么 $|i-j| \leq 15$ .

這樣一來(lái), 我們可以在 $O(n)$ 的時(shí)間內(nèi)找到所有距離不超過(guò) $\delta$ 的點(diǎn)對(duì), 并記錄距離最小的點(diǎn)對(duì)作為結(jié)果輸出(如果存在). 思路思路如下:

pairs_within_delta = []  # S中距離不超過(guò)delta的點(diǎn)的集合
for s in Sy:
    for t in 15 points after s:
        if d(s, t) < delta:
            add (s,t) to pairs_within_delta
output the minimum distance pair in pairs_within_delta

求解子問(wèn)題 $Q$ 和 $R$ 之前, 首先把 $P$ 根據(jù) $y$ 軸從小到大排序得到 $P_y$ , 這樣一來(lái)可以在 $O(n)$ 時(shí)間內(nèi)構(gòu)造 $S_y$ , 即依次過(guò)濾掉 $P_y$ 中距離 $L$ 超過(guò) $\delta$ 的點(diǎn). 在上述算法中, 外層循環(huán)次數(shù)是 $O(n)$ , 內(nèi)層循環(huán)是常數(shù), 因此在合并步驟中構(gòu)造closest pair的時(shí)間復(fù)雜度最終降低為 $O(n)$ .

Python實(shí)現(xiàn)

先把輸入點(diǎn)集 $P$ 分別按 $x$ 軸和 $y$ 軸排序, 得到 $P_x$ 和 $P_y$ . 遞歸求解的過(guò)程參考函數(shù)closest_pair_xy.


def closest_pair(points):
    """ 計(jì)算二維點(diǎn)集中的closest pair.
    :param points: P = [(x1,y1), (x2,y2), ..., (xn, yn)]
    :return: 兩個(gè)距離最近的點(diǎn)
    """
    
    # 把P按x軸和y軸分別進(jìn)行排序, 得到Px和Py
    # 注意: P, Px, Py 三個(gè)集合是相同的(僅僅排序不同)
    Px = sorted(points, key=lambda item: item[0])
    Py = sorted(points, key=lambda item: item[1])
    return closest_pair_xy(Px, Py)
    
    
def closest_pair_xy(Px, Py):
    """ 計(jì)算closest pair
    :param Px: 把points按x軸升序排列
    :param Py: 把points按y軸升序排列
    :return: point1, point2
    """
    if len(Px) <= 3:
        return search_closest_pair(Px)
    # 構(gòu)造子問(wèn)題的輸入: Qx, Rx, Qy, Ry
    k = len(Px) // 2
    Q, R = Px[0: k], Px[k:]
    Qx, Qy = sorted(Q, key=lambda x: x[0]), sorted(Q, key=lambda x: x[1])
    Rx, Ry = sorted(R, key=lambda x: x[0]), sorted(R, key=lambda x: x[1])
    # 求解子問(wèn)題
    q0, q1 = closest_pair_xy(Qx, Qy)
    r0, r1 = closest_pair_xy(Rx, Ry)
    # 合并子問(wèn)題的解
    return combine_results_of_sub_problems(Py, Qx, q0, q1, r0, r1)


def search_closest_pair(points):
    """ 用枚舉的方式尋找closest pair
    :param points: [(x1,y1), (x2,y2), ...]
    :return: closest pair
    """
    n = len(points)
    dist_min, i_min, j_min = math.inf, 0, 0
    for i in range(n-1):
        for j in range(i+1, n):
            d = get_dist(points[i], points[j])
            if d < dist_min:
                dist_min, i_min, j_min = d, i, j
    return points[i_min], points[j_min]


def get_dist(a, b):
    """ 計(jì)算兩點(diǎn)之間的歐式距離
    """
    return math.sqrt(math.pow(a[0]-b[0], 2) + math.pow(a[1]-b[1], 2))

設(shè) $T(n)$ 代表closest_pair_xy的計(jì)算時(shí)間. 根據(jù)前文分析, 合并子問(wèn)題的解并輸出原問(wèn)題的解的時(shí)間復(fù)雜度為 $O(n)$ , 因此我們有
$T(n) \leq 2T(n/2) + cn, \quad c \text{ is constant}.$
根據(jù)Master Theorem, 我們有 $T(n) = \Theta(n\log n)$ . 此外, 把 $P$ 分別按 $x,y$ 軸排序的時(shí)間復(fù)雜度為 $O(n\log n)$ , 因此算法整體的時(shí)間復(fù)雜度是 $O(n\log n)$ .

下面是合并過(guò)程的實(shí)現(xiàn).

def combine_results_of_sub_problems(Py, Qx, q0, q1, r0, r1):
    """
    :param Py: P按y軸排序的結(jié)果
    :param Qx: P在x=x0處被切分成Q和R. Qx是Q按x軸排序的結(jié)果
    :param q0: (q0, q1)是Q中的closest pair
    :param q1: 參考q0
    :param r0: (r0, r1)是R中的closest pair
    :param r1: 參考r0
    :return: closest pair in P
    """
    # 計(jì)算Sy
    d = min(get_dist(q0, q1), get_dist(r0, r1))
    Sy = get_sy(Py, Qx, d)
    # 檢查是否存在距離更小的pair
    s1, s2 = closest_pair_of_sy(Sy)
    if s1 and s2 and get_dist(s1, s2) < d:
        return s1, s2
    elif get_dist(q0, q1) < get_dist(r0, r1):
        return q0, q1
    else:
        return r0, r1


def get_sy(Py, Qx, d):
    """ 根據(jù)Py計(jì)算Sy.
    :param Py: P按y軸排序的結(jié)果
    :param Qx: P在x=x0處被切分成Q和R. Qx是Q按x軸排序的結(jié)果
    :param d: delta
    :return: S
    """
    x0 = Qx[-1][0]  # Q最右邊點(diǎn)的x坐標(biāo)值
    return [p for p in Py if p[0] - x0 < d]


def closest_pair_of_sy(Sy):
    """ 計(jì)算集合Sy的closest pair
    """
    n = len(Sy)
    if n <= 1:
        return None, None
    dist_min, i_min, j_min = math.inf, 0, 0
    for i in range(n-1):
        for j in range(i + 1, i + 16):
            if j == len(Sy):
                break
            d = get_dist(Sy[i], Sy[j])
            if d < dist_min:
                dist_min, i_min, j_min = d, i, j
    return Sy[i_min], Sy[j_min]

完整代碼

定理證明

定理如果存在 $s_i, s_j \in S_y$ 滿足 $d(s_i,s_j) < \delta$ , 那么 $|i-j| \leq 15$ .

根據(jù)前文的描述, 已知 $S$ 中的點(diǎn)在下圖藍(lán)色虛線之間. 把 $S$ 中的點(diǎn)按 $y$ 軸從小到大排序得到 $S_y = \{s_1, s_2, \ldots\}$ , 其中 $s_i$ 代表平面中的一個(gè)點(diǎn). 為了方便描述, 我們把下圖中藍(lán)色虛線之間用單位長(zhǎng)度為 $\delta/2$ 的網(wǎng)格劃分.
[圖片上傳失敗...(image-dad441-1586865336187)]
假設(shè)存在 $s_i,s_j$ 使得 $d(s_i, s_j) < \delta$ . 我們要證明 $|i-j| \leq 15$ . 證明分為兩步:

$s_i$ 和 $s_j$ 必須在不同的網(wǎng)格中. 反證法. 假設(shè) $s_i, s_j$ 在同一個(gè)網(wǎng)格中(意味著 $s_i,s_j\in P$ or $Q$ ), 它們的距離 $d(s_i, s_j) \leq \frac{\delta}{2}\sqrt{2} < \delta$ . 注意 $\delta$ 是 $P$ 和 $Q$ 中的最短距離, 因此矛盾.
$|i-j|\leq 15$ . 反證法. 假設(shè) $|i-j| \geq 16$ . 如上圖所示 $s_i$ 和 $s_j$ 之間至少相差3行(網(wǎng)格). 因此 $d(s_i, s_j) \geq \frac{\delta}{2} \cdot 3 > \delta$ , 矛盾.

參考文獻(xiàn)

T.H. Cormen, C. E. Leiserson, R.L. Rivest and C. Stein. Introduction to Algorithms. Third edition. The MIT Press, 2009. ?
J. Kleinberg and E. Tardos. Algorithm Design. Pearson, 2006. ? ?

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者

人面猴
序言：七十年代末纸厉，一起剝皮案震驚了整個(gè)濱河市环揽，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌霍比，老刑警劉巖腊脱，帶你破解...
沈念sama閱讀 222,729評(píng)論 6贊 517
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件土砂，死亡現(xiàn)場(chǎng)離奇詭異，居然都是意外死亡氮凝，警方通過(guò)查閱死者的電腦和手機(jī)羔巢，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 95,226評(píng)論 3贊 399
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)罩阵，“玉大人竿秆，你說(shuō)我怎么就攤上這事「灞冢” “怎么了幽钢？”我有些...
開(kāi)封第一講書(shū)人閱讀 169,461評(píng)論 0贊 362
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵，是天一觀的道長(zhǎng)傅是。經(jīng)常有香客問(wèn)我匪燕，道長(zhǎng)，這世上最難降的妖魔是什么喧笔？我笑而不...
開(kāi)封第一講書(shū)人閱讀 60,135評(píng)論 1贊 300
?港島之戀（遺憾婚禮）
正文為了忘掉前任帽驯，我火速辦了婚禮，結(jié)果婚禮上书闸，老公的妹妹穿的比我還像新娘尼变。我一直安慰自己，他們只是感情好浆劲，可當(dāng)我...
茶點(diǎn)故事閱讀 69,130評(píng)論 6贊 398
惡毒庶女頂嫁案：這布局不是一般人想出來(lái)的
文/花漫我一把揭開(kāi)白布嫌术。她就那樣靜靜地躺著，像睡著了一般牌借。火紅的嫁衣襯著肌膚如雪度气。梳的紋絲不亂的頭發(fā)上，一...
開(kāi)封第一講書(shū)人閱讀 52,736評(píng)論 1贊 312
城市分裂傳說(shuō)
那天走哺，我揣著相機(jī)與錄音蚯嫌，去河邊找鬼。笑死丙躏，一個(gè)胖子當(dāng)著我的面吹牛，可吹牛的內(nèi)容都是我干的束凑。我是一名探鬼主播晒旅，決...
沈念sama閱讀 41,179評(píng)論 3贊 422
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開(kāi)眼，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼汪诉！你這毒婦竟也來(lái)了废恋？” 一聲冷哼從身側(cè)響起谈秫，我...
開(kāi)封第一講書(shū)人閱讀 40,124評(píng)論 0贊 277
萬(wàn)榮殺人案實(shí)錄
序言：老撾萬(wàn)榮一對(duì)情侶失蹤，失蹤者是張志新（化名）和其女友劉穎鱼鼓，沒(méi)想到半個(gè)月后拟烫，有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體，經(jīng)...
沈念sama閱讀 46,657評(píng)論 1贊 320
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡迄本，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 38,723評(píng)論 3贊 342
?白月光啟示錄
正文我和宋清朗相戀三年硕淑，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片嘉赎。...
茶點(diǎn)故事閱讀 40,872評(píng)論 1贊 353
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡置媳，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出公条，到底是詐尸還是另有隱情拇囊，我是刑警寧澤，帶...
沈念sama閱讀 36,533評(píng)論 5贊 351
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布靶橱，位于F島的核電站寥袭，受9級(jí)特大地震影響，放射性物質(zhì)發(fā)生泄漏关霸。R本人自食惡果不足惜纠永，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 42,213評(píng)論 3贊 336
男人毒藥：我在死后第九天來(lái)索命
文/蒙蒙一、第九天我趴在偏房一處隱蔽的房頂上張望谒拴。院中可真熱鬧尝江，春花似錦、人聲如沸英上。這莊子的主人今日做“春日...
開(kāi)封第一講書(shū)人閱讀 32,700評(píng)論 0贊 25
一樁弒父案，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽(yáng)苍日。三九已至惭聂，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間相恃，已是汗流浹背辜纲。一陣腳步聲響...
開(kāi)封第一講書(shū)人閱讀 33,819評(píng)論 1贊 274
情欲美人皮
我被黑心中介騙來(lái)泰國(guó)打工，沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留拦耐，地道東北人耕腾。一個(gè)月前我還...
沈念sama閱讀 49,304評(píng)論 3贊 379
代替公主和親
正文我出身青樓，卻偏偏與公主長(zhǎng)得像杀糯，于是被迫代替她去往敵國(guó)和親扫俺。傳聞我的和親對(duì)象是個(gè)殘疾皇子，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 45,876評(píng)論 2贊 361

算法設(shè)計(jì)技巧: 分治法 (Divide & Conquer)

Counting Inversions[2]

Closest Pair[2]

參考文獻(xiàn)

推薦閱讀更多精彩內(nèi)容

Counting Inversions^[2]

Closest Pair^[2]