第四章 分治策略

• 为解决问题，可以将分解为等子问题，通过解决子问题再组合得到问题的解。（子问题是一种递归思想）

寻找最大值最小值MINMAX

• 对于数组最简单的是一次遍历得到和，比较次数为（不展开说明）；利用分治策略，我们只需要次比较就可以得到结果。
• 思路是：每次将A分为两半，在每一半中找到最大值和最小值，并返回两个最小值的最小值，两个最大值的最大值，将大问题逐步分解为小问题。

MINMAX

输入：n个整数元素的数组A[1···n]，n为2的幂。

输出：(x, y)，A中的最大元素和最小元素。

minmax(1, n)

过程 minmax(low, high)
if high - low = 1 then #此时子问题是两个数的比较，易得min和max
    if A[low] < A[high] then return (A[low], A[high])
    else return (A[high], A[low])
    end if
else
    mid <- (low + high) / 2
    (x1, y1) <- minmax(low, mid)
    (x2, y2) <- minmax(mid+1, high) #分别递归处理左半边和右半边
    x <- min{x1, x2} #仅在line10、line11进行元素比较
    y <- max{y1, y2}
    return (x, y)
end if

• 设表示算法在数组上的比较次数，元素的比较仅发生在，而递归调用的比较次数是，即：

  

  

  

合并排序MERGESORT

• 思路是：将n个元素的数组分为两个n/2的子数组，递归分解并对子数组排序，最后将两个子数组递归合并就可以得到最终的有序序列。

MERGESORT

输入：n个元素的数组A[1···n]。

输出：按非降序排列的数组A[1···n]。

mergesort(A, 1, n)

过程 mergesort(low, high)
if low < high then
    mid <- (low + high) / 2
    mergesort(A, low, mid)
    mergesort(A, mid+1, high)
    MERGE(A, low, mid, high)
end if

zEzvFI.md.png

zVSef0.md.png

• 时间复杂度分析：分解步骤仅仅计算，需要常量时间；解决步骤需要递归解决个规模为的子问题，贡献；合并步骤的问题总规模为，根据MERGE算法可知贡献时间：

  

  计算得：MERGESORT算法的时间复杂度为。

寻找中项和第k小的元素SELECT

• 对于已经排序好的（非降序）数组，为奇数，中项为第个元素；为偶数，中项为第个元素；综上，中项为第个元素。寻找中项可以先排序再取中项，但时间复杂度较高（）。

• 寻找中项是寻找第k小元素的一个特例，下面我们解决寻找第k小元素的问题。

• 思路是：如果元素个数小于预定义的阈值44，我们把个元素划分为组（不一定是五组，取决于阈值）。每组包含五个元素，如果不是的倍数，则排除剩余元素，这应当不影响算法的执行，对每组进行排序得到其中项元素，然后将这些中项中的中项记为mm；然后依据mm将数组A分为大于、小于、等于三个子数组，判断第小的元素在哪一部分，返回或者在子数组内递归。

SELECT

输入：n个元素的数组A[1···n]和整数k。

输出：A中的第k小元素。

select(A, 1, n, k)

过程 select(A, low, high, k)
p <- high - low + 1
if p < 44 then 将A排序return(A[k]) #当元素个数小于阈值时，排序取中项的时间更优
令q <- p / 5。将A分为q组，每组5个元素。如果5不整除p，则排除剩余元素。
将q组中的每一组单独排序，找出中项。所有中项集合记为M。
mm <- select(M, 1, q, q/2) #中项的中项实际上也是寻找第k小元素问题
将A[low···high]分成三组
A1 = {a|a < mm}
A2 = {a|a = mm}
A3 = {a|a > mm}
case #|A|指示数组A的元素个数
|A1| >= k:return select(A1, 1, |A1|, k) #通过mm将A分割后，若|A1| < k则该元素必然不会出现在A1内
|A1| + |A2| >= k:return mm
|A1| + |A2| < k:return select(A3, 1, |A3|, k-|A1|-|A2|)
end case

zVFu11.md.png

zVFMX6.md.png

• SELECT时间复杂度为。

快速排序QUICKSORT

• 快速排序十分高效，具有的平均时间复杂度。它优于MERGESORT算法（合并排序的时间复杂度也为）的一点是：它在原位上排序，即对于被排序的元素不需要额外的存储空间，在数据量很大时优势明显。

划分算法SPLIT

• 对于数组，并且令，我们将划分为大于小于两个部分，称为主元或拆分元素。
• 定义：如果元素既不小于其左边的元素，也不大于其右边的元素，则称在一个适当/正确的位置。显然，数组通过划分后，处在一个适当的位置。

SPLIT

输入：数组A[low···high]。

输出：（1）如果有必要，输出重新排列的数组A；（2）划分元素A[low]的新位置w。

i <- low 
x <- A[low]
for j <- low + 1 to high #基准i和j分别向右移动，当需要交换时i才自增
    if A[j] <= x then #当A[j]需要移动到x右边时，基准加一
        i <- i + 1
        if i != j then swap(A[i], A[j])
    end if
end for
swap(A[low], A[i]) #最终基准i的位置即为x的适当位置
w <- i
return A和w

zVVtVf.png

• SPLIT算法比较只发生在，时间复杂度为。

排序算法QUICKSORT

• 在理解SPLIT算法的基础上，快速排序的思路就是：以对数组进行划分确定的适当位置，然后数组A被分为两个子数组，递归划分。

QUICKSORT

输入：n个元素的数组A[1···n]。

输出：按非降序排列的数组A[1···n]。

quicksort(A, 1, n)

过程 quicksort(A, low, high)
if low < high then
    SPLIT(A[low···high], w)
    quicksort(A, low, w-1)
    quicksort(A, w+1, high)
end if

• 时间复杂度分析

大整数相乘

• 设、是两个位的整数（二进制），传统的乘法算法 需要数字相乘来计算它们的乘积（如下图）。而使用分治策略，时间复杂度能显著减小。

  zZFCKx.md.png

• 我们把每个整数分为两个部分，每部分为位，则和可以重写为，由于做乘法运算相当于简单地左移位，仅需要的时间。

  zZFiqK.png

• 时间复杂度分析：

  1. 为4次位的乘法，时间为；
  2. ，左移位，时间为；
  3. 为位加法，时间为；
  4. ，左移位，时间为；
  5. 三个式子相加，时间为；

  所以

  ，与传统乘法并无改进，如何降低呢？

• 我们考虑，又可以化简为：，这样乘法运算被简化为次位的乘法和次加减运算（，注意被重复利用）。

• 改进后

  计算得到，这是对传统方法的一个显著改进。

矩阵乘法

• 令是两个的矩阵，计算。

传统算法

• 传统方法中，利用线性代数知识：

  zZA3CQ.png

• 易知，算法需要乘法运算、次加法运算，时间复杂度为。

递归算法

• 假定，那么我们可以将划分为个大小为的子矩阵

  

  

  需要次的矩阵乘法，次的矩阵加法，递推式如下：

  

  计算得，递归并不产生更有效的算法。

STRASSEN算法

• Strassen矩阵算法在于减少子矩阵相乘的次数，实际上该算法只进行了次矩阵乘法、次矩阵的加法。

  zZV01J.md.png
  zZVh1H.png

• 时间复杂度为。

最近点对问题

• 给定平面上的点集，（内点的个数为）。任意连接其中两点，我们需要找到点集中的最短距离（，欧几里得距离）。

• 采用暴力算法依次计算全部的欧几里得距离，时间复杂度为，下面介绍一种时间复杂度为的算法。

  zZnpDA.md.png

  • 第一步，我们以坐标增序对的点排序，接着将分割成两个子集，使得。通俗地理解，就是在轴的中点画一条平行轴的线。

  • 最近距离可能出现在中，或者中，或者一个点在，一个点在。我们可以通过递归计算出集合的最短距离，对于横跨两个子集的情况，我们如果采用暴力算法，最坏情况下时间并不能得到有效提升。

  • 我们再讲依据，划分为，若存在则一定在新的子区域中。不是区域中所有的点需要比较，只需要比较距小于的。假设，则存在两点使得。

    zZl2NR.png

  • 易知，必在右区域的的矩形上，依据鸽舍原理，在该矩形上最多存在个点。所以中的每个点至多进行次距离计算。

    zZQW6S.png

  • 我们如何找到所需比较的个点呢？将T集合内的点按坐标递增排序。不难发现对于中的每个，与它坐标轴递增的个点比较。

  • 因而，得。这并不是我们先前提到的界。我们注意到若能降低对的排序耗时到，则算法的时间复杂度将为。所以我们可以在初始阶段，对坐标排序（存储在数组）同时对坐标进行排序（存储在数组），即可成功简化。

    ，计算得，归纳为算法CLOSESTPAIR。

算法CLOSESTPAIR

CLOSESTPAIR

输入：平面上n个点的集合S。

输出：S中两点的最小距离。

以x坐标增序对S中的点排序。
Y <- 以y坐标增序对S中的点排序。
delta <- cp(1, n)

过程 cp(low, high)
if high-low+1 <= 3 then 用暴力算法计算delta。
else
    mid <- (low + high) / 2
    x0 <- x(S[mid])
    delta_l <- cp(low, mid)
    delta_r <- cp(mid+1, high)
    delta <- min(delta_l, delta_r)
    k <- 0
    for i <- 1 to n #从Y集合中得到T集合
        if |x(Y[i])-x0| <= delta then
            k <- k + 1 #k指示T的大小
            T[k] <- Y[i]
        end if
    end for
    delta_ <- 2 * delta
    for i <- 1 to k-1 #两层for循环遍历T中的点
        for j <- i+1 to min{i+6, k} #内层循环找六个点（如果k更小则找k个点）
            if d(T[i], T[j]) < delta_ then delta_ <- d(T[i], T[j])
        end for
    end for
    delta <- min(delta, delta_)
end if
return delta