MIT 6006 Lecture 1——算法思维，峰值寻找

一个人思虑太多，就会失去做人的乐趣。

概述

本课程中我们将考虑大规模问题的高效解法，即考虑规模性。本课程的结构如下：

• 算法思想
• 排序/树
• 哈希
• 数论：加密解密算法
• 图
• 最短路径
• 动态规划：图像压缩
• 高级话题

峰值算法

一维峰值算法

问题

考虑下面的一维数组，其中$a-i$为数字：

极值点的定义为：

$$\begin{equation} \textrm{if}\ \ \ \ b\ge a\ \ \ \ \textrm{and}\ \ \ \ b\ge c \\ \textrm{then}\ b\ \textrm{is the peak point} \end{equation}$$

当然，如果在边界上，那么只需要大于一侧即可。我们的问题是：如果峰值点存在，找到峰值点。

解法

最直接的解法就是遍历每一个元素，然后根据定义看一下是否为峰值，其复杂度为$O(n)$，现在我们来看看一个更高效的解法：分治法。

if a[n/2] < a[n/2-1] 
    在 1...n/2-1 中寻找peak，一定会有
else if a[n/2] < a[n/2+1] 
    在 n/2+1...n 中寻找peak
else
    a[n/2] 是极值点

时间复杂度分析

假设我们的算法是正确的，那么其时间复杂度为：

$$\begin{equation} \begin{aligned} T(n) =& T(n/2)+\Theta(1)\\ T(1) =& \Theta(1) \end{aligned} \end{equation}$$

故：

$$\begin{equation} \begin{aligned} T(n) =& T(n/2)+\Theta(1)\\ =& T(n/4)+2\Theta(1)\\ ...&\\ =&T(n/2^{\log_2n})+(\log_2n)\Theta(1)\\ =&\Theta(\log _2n) \end{aligned} \end{equation}$$

二维峰值算法

问题

考虑下面的二维数组：

假定$a$为峰值点，那么$a\ge b, a\ge c, a\ge d,a\ge e$。

解法

解法1：贪心

我们使用贪心算法解决这个问题，假设我们的矩阵为：

我们的策略是，总是沿着最大的路径走，例如从12开始，我们向13搜索，依次走过14->15->16…直到20为止。该算法的时间复杂度为$\Theta(nm)$。

解法2：分治法

考虑这样的解法：我们先选取中间列，令$j=m/2$，找到一个位于$(i,j)$的一维峰值点，然后以$(i,j)$为基准，再找到这一行的一维峰值点，这样能找到二维的峰值点吗？

答案是不行，这个解法是错误的，以我们上面的图为例，假设12是该列的一个峰值点，而当我们搜索12所在的行时，最终找到的峰值点是14，但是14并不是一个二维峰值点，所以该算法是错的。我们给出正确的贪心规则：

选取中间列 j=m/2
找到该列的全局最大值 (i,j)
比较(i,j-1), (i,j), (i,j+1)
if (i,j-1) > (i,j)
    选择左半列
if (i,j+1) > (i,j)
    选择右半列
else 
    选择(i,j)

在上面的伪代码中，else部分可以直接返回极值点，是因为$(i,j)$为该列的最大值，所以比$(i-1,j),(i+1,j)$都要大，而该点又比$(i,j-1),(i,j+1)$大，故符合峰值定义，可以直接返回。当只有一列时，最大值即峰值，这个是基例。

时间复杂度分析

上面的算法时间复杂度计算如下：

$$\begin{equation} \begin{aligned} T(n,m) &= T(n,m/2)+\Theta(n)\\ T(n,1) &=\Theta(n)\\ T(n,m) &=\Theta(n)+...+\Theta(n) = \Theta(n\log_2m) \end{aligned} \end{equation}$$

题目及题解

题目

一：将下列函数根据时间复杂度进行排序

第一组

$$\begin{equation} \begin{aligned} f_1(n)&=n^{0.999999}\log n\\ f_2(n)&=10000000n\\ f_3(n)&=1.000001^n\\ f_4(n)&=n^2\\ \end{aligned} \end{equation}$$

解

$$\begin{equation} \begin{aligned} \frac{f_1}{f_2}&=\frac{n^{1-0.0000001}\log n}{10000000n}\\ &=C_1\frac{\log n}{n^{0.0000001}}\\ \end{aligned} \end{equation}$$

由于$n\rightarrow \infin$时$\log n$与$n^{0.0000001}$趋近于无穷大，所以对上式使用洛必达法则：

$$\begin{equation} \begin{aligned} \underset{n\rightarrow \infin}{\lim}\frac{f_1}{f_2}&=\underset{n\rightarrow \infin}{\lim}\frac{f_1'}{f_2'}\\ &=\underset{n\rightarrow \infin}{\lim}\frac{1}{n^{0.0000001}}\\ &=0 \end{aligned} \end{equation}$$

故$\Theta(f_1)\le\Theta(f_2)$。同理易得$\Theta(f_2)\le\Theta(f_3)$，$\Theta(f_2)\le\Theta(f_4)$，而$\Theta(f_4)\le\Theta(f_3)$，故上述公式时间复杂度排序为：$\Theta(f_1)\le\Theta(f_2)\le\Theta(f_4)\le\Theta(f3)$

第二组

$$\begin{equation} \begin{aligned} f_1(n)&=2^{2^{1000000}}\\ f_2(n)&=2^{100000n}\\ f_3(n)&=C_n^2\\ f_4(n)&=n\sqrt n\\ \end{aligned} \end{equation}$$

解

常数时间复杂度为$\Theta(1)$为最小，$f_2$时间复杂度最高，为$\Theta(2^n)$，现比较$f_3$和$f_4$，$f_3=\frac{n(n-1)}{2}$，故

$$\begin{equation} \begin{aligned} \underset{n\rightarrow \infin}{\lim}\frac{f_3}{f_4}&=\underset{n\rightarrow \infin}{\lim}\frac{n(n-1)} {2n\sqrt n}\\ &=\frac{\sqrt n}{2}-\frac{1}{2\sqrt n}\\ &=\infin \end{aligned} \end{equation}$$

所以排序结果为$\Theta(f_1)\le\Theta(f_4)\le\Theta(f_3)\le\Theta(f2)$.

第三组

$$\begin{equation} \begin{aligned} f_1(n)&=n^{\sqrt n}\\ f_2(n)&=2^{n}\\ f_3(n)&=n^{10}2^{n/2}\\ f_4(n)&=\sum_{i=1}^{n}(i+1)\\ \end{aligned} \end{equation}$$

这个算极限比较麻烦，采用matlab求两两之间的极限，代码如下：

syms n
f1 = n^sqrt(n)
f2 = 2^n
f3 = n^10*2^(n/2)
f4 = (1+n)*n/2+n

f1_f2 = f1/f2
f1_f3 = f1/f3
f1_f4 = f1/f4
f2_f3 = f2/f3
f2_f4 = f2/f4
f3_f4 = f3/f4
limit(f1_f2, n, inf)   #对f1/f2求极限，结果为0，即O(f1) <= O(f2)
...

最终结果为：$\Theta(f_4)\le\Theta(f_1)\le\Theta(f_3)\le\Theta(f_2)$

二：递归复杂度求解

第一题

已知：

$$\begin{equation} \begin{aligned} T(x,c) &= \Theta(x)\ \ \ \ \ \ \ \ \ \textrm{for}\ \ c\le2\\ T(c,y) &= \Theta(y)\ \ \ \ \ \ \ \ \ \textrm{for}\ \ c\le2\\ T(x,y) &=\Theta(x+y)+T(x/2,y/2) \end{aligned} \end{equation}$$

求$T(n,n)$的时间复杂度

解：

$$\begin{equation} \begin{aligned} T(x,y)&=\Theta(x+y)+T(x/2,y/2)\\ &=\Theta(x+y)+\Theta(x/2+y/2)+T(x/4,y/4)\\ &=\Theta(x+y)+\Theta(x/2+y/2)+\Theta(x/4+y/4)+...\\ &=\Theta(2x+2y) \end{aligned} \end{equation}$$

故$T(n,n)=\Theta(n)$。

第二题

已知：

$$\begin{equation} \begin{aligned} T(x,c) &= \Theta(x)\ \ \ \ \ \ \ \ \ \textrm{for}\ \ c\le2\\ T(c,y) &= \Theta(y)\ \ \ \ \ \ \ \ \ \textrm{for}\ \ c\le2\\ T(x,y) &=\Theta(x)+T(x,y/2) \end{aligned} \end{equation}$$

解：

$$\begin{equation} \begin{aligned} T(x,y)&=\Theta(x)+T(x,y/2)\\ &=\Theta(x)+\Theta(x)+T(x,y/4)\\ &=\underset{\log y个\Theta(x)}{\underbrace{\Theta(x)+\Theta(x)+...+\Theta(x)}}\\ &=\Theta(x\log y) \end{aligned} \end{equation}$$

故$T(n,n)=\Theta(n\log n)$。

第三题

$$\begin{equation} \begin{aligned} T(x,c) &= \Theta(x)\ \ \ \ \ \ \ \ \ \textrm{for}\ \ c\le2\\ T(x,y) &= \Theta(x)+S(x,y/2)\\ S(c,y) &= \Theta(y)\ \ \ \ \ \ \ \ \ \textrm{for}\ \ c\le2\\ S(x,y) &= \Theta(y)+T(x/2,y) \end{aligned} \end{equation}$$

解

$$\begin{equation} \begin{aligned} T(x,y)&=\Theta(x)+\Theta(y/2)+T(x/2,y/2)\\ &=\Theta(x)+\Theta(y/2)+\Theta(x/2)+\Theta(y/4)+...\\ &\le\Theta(2x+y) \end{aligned} \end{equation}$$

故$T(n,n)=\Theta(n)$

代码

向量峰值搜索代码

class Solution {
    int findPeakElement(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        while (l < r) {
            int mid = (l + r) / 2;
            if (nums[mid] > nums[mid + 1])     //由于除法是向下取整，这意味着我们得到的mid都是左mid
                                               //因此mid+1一定是存在的
                r = mid;
            else
                l = mid + 1;
        }
        return l;
    }
}

矩阵峰值搜索代码

方法一：分治法

根据上面的分治法，我们可以写出如下代码：

def algorithm1(problem, trace = None):
    # if it's empty, we're done 
    if problem.numRow <= 0 or problem.numCol <= 0:
        return None

    # the recursive subproblem will involve half the number of columns
    mid = problem.numCol // 2

    # information about the two subproblems
    (subStartR, subNumR) = (0, problem.numRow)
    (subStartC1, subNumC1) = (0, mid)
    (subStartC2, subNumC2) = (mid + 1, problem.numCol - (mid + 1))

    subproblems = []
    subproblems.append((subStartR, subStartC1, subNumR, subNumC1))   # 子问题一：左侧部分
    subproblems.append((subStartR, subStartC2, subNumR, subNumC2))   # 子问题二：右侧部分

    # get a list of all locations in the dividing column
    divider = crossProduct(range(problem.numRow), [mid])   # 利用笛卡尔积针对一列进行划分，得到该列元素所有坐标

    # find the maximum in the dividing column
    bestLoc = problem.getMaximum(divider, trace)           # 获得该列的最大值

    # see if the maximum value we found on the dividing line has a better
    # neighbor (which cannot be on the dividing line, because we know that
    # this location is the best on the dividing line)
    neighbor = problem.getBetterNeighbor(bestLoc, trace)   # 找到更大的左右邻居

    # this is a peak, so return it                         左右邻居不存在，当前点即为峰值点
    if neighbor == bestLoc:
        if not trace is None: trace.foundPeak(bestLoc)
        return bestLoc
   
    # otherwise, figure out which subproblem contains the neighbor, and
    # recurse in that half
    sub = problem.getSubproblemContaining(subproblems, neighbor)  # 判断向左还是向右搜索
    if not trace is None: trace.setProblemDimensions(sub)
    result = algorithm1(sub, trace)                         # 解决子问题
    return problem.getLocationInSelf(sub, result)

证明

为了证明算法总是能找到峰值，我们需要证明如下两条陈述：

1. 如果矩阵非空，那么算法1总能返回一个位置

2. 如果算法1返回了一个位置，那么这个位置一定是峰值点

证明第一点：

假设矩阵为$n\times n$，那么递归子问题的规模为$m \times\left \lfloor n/2 \right \rfloor$，所以递归子问题中列数随着递归过程是严格递减的。所以算法最终会返回一个点，或者最后进入一个列为0的子问题而不返回任何一个位置，故如果算法1存在不返回位置的情况，那么一定有子问题列数为0，下面我们证明这种情况不可能发生。如果算法确实处理了一个空的子问题，那么该问题的上一步子问题规模一定为$m\times 1$或者$m\times2$，下面分类讨论

(1) 如果为$m\times1$，那么计算中心列的最大值即为计算整个子数组的最大值，而子数组的最大值是一定存在的，所以一定会返回一个峰值点。

(2) 如果为$m\times2$，那么又存在两种情况，第一，中心列的最大值即为峰值点，那么会返回峰值的位置；第二，中心列的最大值不是峰值点，那么算法又会进一步递归，处理一个$m\times1$的子问题，一定会返回一个峰值点。

综上，算法一定会返回一个点。

证明第二点：

假设我们返回的点为$(r_1,c_1)$，那么该点一定是$c_1$列上最大的，如果该点不是峰值点，那么算法会以$(r_1,c_1)$为起点进入下一个递归中，同时，根据算法的规则，存在与$c_1$相邻的$c_2$（$|c1-c2|= 1$），满足$val(r_1,c_1) < val(r_1,c_2)$，令$(r_2,c_2)$为$c_2$列上的最大值，有$val(r_1,c_2)\le val(r_2,c_2)$。因为算法执行到了包含$(r_1,c_1)$的一侧，所以一定有$val(r_2,c_2)<val(r_2,c_1)$，所以

$$val(r_1,c_1)<val(r_1,c_2)\le val(r_2,c_2)<val(r_2,c_1)$$

但是$(r_1,c_1)$又是该列最大的，所以产生了矛盾，所以$(r_1,c_1)$一定是峰值点。

复杂度分析

根据前面的结果，分治法的时间复杂度为$\Theta(n\log n)$

方法二：贪心上升法

def algorithm2(problem, location = (0, 0), trace = None):
    # if it's empty, we're done 
    if problem.numRow <= 0 or problem.numCol <= 0:
        return None

    nextLocation = problem.getBetterNeighbor(location, trace)

    if nextLocation == location:
        # there is no better neighbor, so return this peak
        if not trace is None: trace.foundPeak(location)
        return location
    else:
        # there is a better neighbor, so move to the neighbor and recurse
        return algorithm2(problem, nextLocation, trace)

方法二的逻辑很简单，一直找比当前节点更大的相邻节点，直到找不到为止。

证明

在贪心算法中，我们的搜索过程是单调递增的，由于数组的大小是有限的，那么数组中的数存在上界，我们一定能够找到一个位置，且该位置一定是一个峰值点。

复杂度分析

设二维矩阵大小为$n\times n$，假设$a(i,j)$为当前搜索位置，那么下一个搜索位置$a_{next}$的完整递归定义为：

$$\begin{equation} \begin{aligned} a_{next} = \left\{\begin{matrix} a(i,j) & a(i,j)\ \textrm{is the peak}\\ \max(a(i-1,j),a(i+1,j),a(i,j-1),a(i,j+1)) & a(i,j)\ \textrm{is not the peak} \end{matrix}\right. \end{aligned} \end{equation}$$

从递归中可知，最坏的情况下，需要遍历所有的网格，所以时间复杂度为$\Theta(n^2)$。

方法三：改进的分治法（错误）

在分治法中，我们将矩阵分为了左右两个部分，寻找极值点，那么我们能不能进一步分割呢？比如不再是二分割，而是将矩阵四分割，横纵坐标各切一刀，将矩阵分为四个部分，依次在四个部分中寻找极值点？代码如下：

def algorithm3(problem, bestSeen = None, trace = None):
    # if it's empty, we're done 
    if problem.numRow <= 0 or problem.numCol <= 0:
        return None

    midRow = problem.numRow // 2
    midCol = problem.numCol // 2

    # first, get the list of all subproblems
    subproblems = []

    (subStartR1, subNumR1) = (0, midRow)
    (subStartR2, subNumR2) = (midRow + 1, problem.numRow - (midRow + 1))
    (subStartC1, subNumC1) = (0, midCol)
    (subStartC2, subNumC2) = (midCol + 1, problem.numCol - (midCol + 1))

    subproblems.append((subStartR1, subStartC1, subNumR1, subNumC1))
    subproblems.append((subStartR1, subStartC2, subNumR1, subNumC2))
    subproblems.append((subStartR2, subStartC1, subNumR2, subNumC1))
    subproblems.append((subStartR2, subStartC2, subNumR2, subNumC2))

    # find the best location on the cross (the middle row combined with the
    # middle column)
    cross = []

    cross.extend(crossProduct([midRow], range(problem.numCol)))
    cross.extend(crossProduct(range(problem.numRow), [midCol]))

    crossLoc = problem.getMaximum(cross, trace)
    neighbor = problem.getBetterNeighbor(crossLoc, trace)

    # update the best we've seen so far based on this new maximum
    if bestSeen is None or problem.get(neighbor) > problem.get(bestSeen):
        bestSeen = neighbor
        if not trace is None: trace.setBestSeen(bestSeen)

    # return if we can't see any better neighbors
    if neighbor == crossLoc:
        if not trace is None: trace.foundPeak(crossLoc)
        return crossLoc

    # figure out which subproblem contains the largest number we've seen so
    # far, and recurse
    sub = problem.getSubproblemContaining(subproblems, bestSeen)
    newBest = sub.getLocationInSelf(problem, bestSeen)
    if not trace is None: trace.setProblemDimensions(sub)
    result = algorithm3(sub, newBest, trace)
    return problem.getLocationInSelf(sub, result)

代码逻辑如下，每次在midRow和midCol中找到最大值，然后找到最大值的四邻域中的最大值，如果上下左右四格都比找到的最大值小，那么最大值即为峰值；如果存在临近的位置比找到的最大值大，那么就到该位置所在的子问题中寻找峰值点。通过将问题分为四个子问题，我们似乎能够递归地找到峰值点结果。但是很遗憾，这个代码是错误的，一个反例如下：

matrix = [[0,0,9,8,0,0,0],
          [0,0,0,0,0,0,0],
          [0,1,0,0,0,0,0],
          [0,2,0,0,0,0,0],
          [0,0,0,0,0,0,0],
          [0,0,0,0,0,0,0],
          [0,0,0,0,0,0,0]]

在上面的例子中，我们先在中间行和列找到了最大值8，然后8的邻居中最大的是9，选择左上子矩阵作为子问题，中心十字最大值为1，而在这个子问题中，1是子矩阵的极值点，但并不是全局极值点。这个解法的根本问题在于，在解决子问题的过程中，子问题边界值的比较是不充分的，在上面的例子中，1是子问题的边界值，但是这个边界值并没有和2进行比较，所以比较不充分，找到了错误的解。

方法四：另一个改进的分治法

def algorithm4(problem, bestSeen = None, rowSplit = True, trace = None):
    # if it's empty, we're done 
    if problem.numRow <= 0 or problem.numCol <= 0:
        return None

    subproblems = []
    divider = []

    if rowSplit:
        # the recursive subproblem will involve half the number of rows
        mid = problem.numRow // 2

        # information about the two subproblems
        (subStartR1, subNumR1) = (0, mid)
        (subStartR2, subNumR2) = (mid + 1, problem.numRow - (mid + 1))
        (subStartC, subNumC) = (0, problem.numCol)

        subproblems.append((subStartR1, subStartC, subNumR1, subNumC))
        subproblems.append((subStartR2, subStartC, subNumR2, subNumC))

        # get a list of all locations in the dividing column
        divider = crossProduct([mid], range(problem.numCol))
    else:
        # the recursive subproblem will involve half the number of columns
        mid = problem.numCol // 2

        # information about the two subproblems
        (subStartR, subNumR) = (0, problem.numRow)
        (subStartC1, subNumC1) = (0, mid)
        (subStartC2, subNumC2) = (mid + 1, problem.numCol - (mid + 1))

        subproblems.append((subStartR, subStartC1, subNumR, subNumC1))
        subproblems.append((subStartR, subStartC2, subNumR, subNumC2))

        # get a list of all locations in the dividing column
        divider = crossProduct(range(problem.numRow), [mid])

    # find the maximum in the dividing row or column
    bestLoc = problem.getMaximum(divider, trace)
    neighbor = problem.getBetterNeighbor(bestLoc, trace)

    # update the best we've seen so far based on this new maximum
    if bestSeen is None or problem.get(neighbor) > problem.get(bestSeen):
        bestSeen = neighbor
        if not trace is None: trace.setBestSeen(bestSeen)

    # return when we know we've found a peak
    if neighbor == bestLoc and problem.get(bestLoc) >= problem.get(bestSeen):
        if not trace is None: trace.foundPeak(bestLoc)
        return bestLoc

    # figure out which subproblem contains the largest number we've seen so
    # far, and recurse, alternating between splitting on rows and splitting
    # on columns
    sub = problem.getSubproblemContaining(subproblems, bestSeen)
    newBest = sub.getLocationInSelf(problem, bestSeen)
    if not trace is None: trace.setProblemDimensions(sub)
    result = algorithm4(sub, newBest, not rowSplit, trace)
    return problem.getLocationInSelf(sub, result)

方法四在方法一的基础上添加了一个bestSeen变量，用于记录上一步操作中最大的值，下面我们对这个方法进行证明。证明过程参考方法一，也是分为两步，第一步证明如果矩阵不为空，那么返回值存在，第二步证明返回值一定是峰值。这里直接证明第二步。

假设我们的返回值为$(r_1,c_1)$，且该点不是峰值点，那么存在$(r_3,c_3)$与$(r_1,c_1)$相邻，且$val(r_3,c_3)>val(r_1,c_1)$，又因为$(r_1,c_1)$为返回值，故存在$(r_2,c_2)\rightarrow (r_1,c_1)$的转换，且$val(r_2,c_2) < val(r_1,c_1)$。但是我们的返回值是$(r_1,c_1)$，所以递归到$(r_3,c_3)$后，又会经过某个递归链从$(r_3,c_3)$到达$(r_2,c_2)$，所以$val(r_3,c_3)<val(r_2,c_2)<val(r_1,c_1)<val(r_3,c_3)$，产生矛盾，故$(r_1,c_1)$一定是峰值点。

参考文献

---

1. 1.第一课视频 ↩
2. 2.第一课作业 ↩