《算法导论》中的分治策略分析

本篇基于《算法导论》第4章的最大子数组问题和归并排序分析分治策略的基本思想、伪代码实现、时间复杂度的求解方法。

概述

分治策略英文为“Divide and Conquer”,将原问题分解为子问题然后递归求解。应用分治策略解决问题时,一般分为如下三个步骤:

  1. 分解:将原问题分解为子问题。大部分情况下,子问题和原问题形式完全一样,但是有时候我们还需要求解与原问题不完全一样的子问题,我们将这样的子问题也看作合并过程(至于为何如此,我的个人理解将在后面写到)。

  2. 解决:递归求解子问题。当子问题足够大时,我们将递归过程中的子问题称为递归情况(recursive case);当子问题变得足够小,不再需要递归时,我们说递归进入了基本情况(base case)。

  3. 合并:将子问题的解组合成原问题的解。

归并排序

伪代码实现

MERGE-SORT(A, p, r)
    if p<r
        q = (p+r)/2
        MERGE-SORT(A, p, q)
        MERGE-SORT(A, q+1, r)
        MERGE(A, p, q, r)

当我们进行归并排序时,我们将原数组均分为两个子数组,递归过程将两个数组各自排序后,MERGE函数将两个数组进行合并。这个递归过程的base case是当p=r时数组中只含有一个元素。

思考的过程是从问题出发,但是设置递归函数参数的时候往往从中间的一个recursive case出发。

MERGE(A, p, q, r)
    n1 = p-q+1
    n2 = r-q
    let L[1...n1 + 1] and R[1...n2 + 1] be new arrays
    for i = 1 to n1
        L[i] = A[p + i - 1]
    for j = 1 to n2
        R[j] = A[q + j]
    L[n1 + 1] = ∞
    R[n2 + 1] = ∞
    i = 1
    j = 1
    for k = p to r:
        if L[i] <= R[j]
            A[k] = L[i]
            i = i + 1
        else
            A[k] = R[j]
            j = j + 1

我认为MERGE函数的这种写法是思路最清晰的:将A空间的两个子数组分别copy,最后从到到尾遍历A空间进行填充。同时因为哨兵的存在,也简化了代码。

复杂度分析

从上述伪代码可以看出,MERGE函数无论如何都将遍历一遍 A[p...q] ,所以归并排序实际上没有最好、最坏、平均情况之分,任何情况下时间复杂度都是 O(nlogn) ,由于每次MERGE结束都将辅助空间释放,且最后一次辅助空间最大为n,所以空间复杂度是 $O(n)$

稳定性分析

归并排序是稳定的。是因为上述的MERGE写法保持了其稳定性,如果将L[i] <= R[j]反过来写,那么其稳定性将无法保证。

最大子数组问题

最容易想到的就是暴力求解,遍历所有的区间选出数组和最大的那一个。

接下来便引出了最大子数组这个核心问题,但是在此之前,我想强调一下这个问题变换,也就是不在从价格数据的角度看待这个问题,而是考察每天的价格变化。从求解问题的角度看,是对输入数据整体的转化,将单独的数据转换为了相互关联的数据。

talk is cheap:

FIND-MAX-CROSSING-SUBARRAY(A, low, mid, high)
    left-sum = -∞
    sum = 0
    for i = mid downto low
        sum = sum + A[i]
        if sum > left-sum
            left-sum = sum
            max-left = i
    right-sum = -∞
    sum = 0
    for j = mid+1 to high
        sum = sum + A[j]
        if sum > right-sum
            right-sum = sum
            max-right = i
    return (max-left, max-right, left-sum + right - sum)
FIND-MAXIMUM-SUBARRAY(A, low, high)
    if high == low
        return (low, high, A[low])  //base case
    else 
        mid = floor((low+high)/2)
        (left-low, left-high, left-sum) = 
                FIND-MAXIMUM-SUBARRAY(A, low, mid)
        (right-low, right-high, right-sum) = 
                FIND-MAXIMUM-SUBARRAY(A, mid+1, high)
        (cross-low, cross-high, cross-sum) = 
                FIND-MAXIMUM-SUBARRAY(A, low, mid, high)
        if left-sum is maxmimum
            return (left-low, left-high, left-sum)
        elseif right-sum is maxmimum
            return (right-low, right-high, right-sum)
        else
            return (cross-low, cross-high, cross-sum)

其实分治策略的本质就是将原问题,或者说将输入转化为若干个部分分别处理。在这个问题中,将输入(经过问题转化之后的)一分为二,答案可能在左半部分,也可能在右半部分,也有可能跨越中间位置。不难发现,前两种情况和原问题是一种类型,可以递归处理;而第三种情况是一种新的问题,不可以递归处理,只好重新写一个函数,而归并排序中MERGE函数也独立于递归之外单独存在,这也就是我理解的为什么将新形式的问题看作合并过程

该问题归并解法(时间复杂度为 $0(nlogn)$ )到这里就结束了,但是该问题可以在线性时间内解决,解决方案文末给出。

分治策略时间复杂度的求解方法

这部分就不展开了,主要有如下三种方法:

  1. 代入法

  2. 递归树法

  3. 主方法

引用:

  1. 《算法导论》第2章、第4章

  2. 线性时间内解决最大子数组问题参考

发表评论

电子邮件地址不会被公开。 必填项已用*标注