问题描述

以一维的情形为例，Peak Finding 描述这样一个问题。

给定一个数组 a，是否能够找到这样一个坐标 i，使得 \(a[i - 1] \le a[i] \le a[i + 1]\)，这样的坐标 i 被称为 peak。

特别地，在边界上的元素只需要保证大于等于与其相邻的一个元素，也被判定为 peak。

---

Straightforward Algorithm

遍历数组，找到是否存在一个位置上的元素，该元素大于等于与其所有的相邻元素。

复杂度 \(\Theta(N)\)。

def peak_finding(a):
    if len(a) == 0:
        return None
    if len(a) == 1 or a[0] >= a[1]:
        return 0
    if a[-1] >= a[-2]:
        return len(a) + 1
    for i in range(1, len(a) - 1):
        left = a[i - 1]
        right = a[i + 1]
        if left <= a[i] <= right:
            return i

---

Divide and Conquer

分而治之算法。考察 \(a[n / 2]\) 及与其相邻的元素。

• 如果 \(a[n / 2]\) 小于其左邻居，则可以在左侧的子数组中递归寻找 peak
• 如果 \(a[n / 2]\) 小于其右邻居，则可以在右侧的子数组中递归寻找 peak
• 如果以上两种情形均不成立，则 \(n / 2\) 就是一个 peak

def peak_finding(a):
    if len(a) == 0:
        return None
    return divide_and_conquer(a, 0, len(a) - 1)

def divide_and_conquer(a, low, high):
    if low >= high:
        return low
    middle = (low + high) // 2
    if a[middle - 1] > a[middle]:
        return divide_and_conquer(a, low, middle - 1)
    elif a[middle + 1] > a[middle]:
        return divide_and_conquer(a, middle + 1, high)
    else:
        return middle

假设 \(T(N)\) 是该算法运行的时间，则有

\[T(N) = T(N / 2) + \Theta(1) = \underbrace{\Theta(1) + \dots + \Theta(1)}_{log(N)} = \Theta(logN) \]

---

问题扩展

问题扩展至二维情形。如上图，当且仅当

\[a \ge x, x \in \{b, c, d, e\} \]

成立时，\(a\) 所在的位置称为 peak。

尝试找出二维情形下的一个 peak。

---

Greedy Ascent Algorithm

从数组的任意位置开始，向数组元素增大的方向移动，直至周围的数组元素均小于当前元素。

复杂度 \(\Theta(MN)\)。

def peak_finding(a):
    if len(a) == 0 or len(a[0]) == 0:
        return None
    if len(a) == 1 or len(a[0]) == 1:
        return (0, 0)
    n = len(a)
    m = len(a[0])
    location = (n // 2, m // 2)
    while True:
        row, column = location
        value = a[row][column]
        if row > 0 and a[row - 1][column] > value:
            location = (row - 1, column)
            continue
        if row < n - 1 and a[row + 1][column] > value:
            location = (row + 1, column)
            continue
        if column > 0 and a[row][column - 1] > value:
            location = (row, column - 1)
            continue
        if column < m - 1 and a[row][column + 1] > value:
            location = (row, column + 1)
            continue
        return location

---

Divide and Conquer

分而治之算法。考察第 \(j = m / 2\) 列。

• 找出这一列上最大的元素 \(a[i][j]\)，将其与其左右相邻的元素比较
• 如果 \(a[i][j - 1] > a[i][j]\)，则可以在左侧的列中递归寻找二维 peak
• 如果 \(a[i][j + 1] > a[i][j]\)，则可以在右侧的列中递归寻找二维 peak
• 如果以上两种情形均不成立，则 \((i, j)\) 就是一个二维 peak

def peak_finding(a):
    if len(a) == 0 or len(a[0]) == 0:
        return None
    m = len(a[0])
    return divide_and_conquer(a, 0, m - 1)

def divide_and_conquer(a, low, high):
    if low >= high:
        row_index = find_max_row_on_column(a, low)
        return row_index, low
    middle = (low + high) // 2
    row_index = find_max_row_on_column(a, middle)
    if a[row_index][middle - 1] > a[row_index][middle]:
        return divide_and_conquer(a, low, middle - 1)
    elif a[row_index][middle + 1] > a[row_index][middle]:
        return divide_and_conquer(a, middle + 1, high)
    else:
        return row_index, middle

def find_max_row_on_column(a, column):
    max_row = 0
    for i in range(len(a)):
        if a[i][column] > a[max_row][column]:
            max_row = i
    return max_row

假设 \(T(N, M)\) 是该算法运行的时间，则有

\[T(N, M) = T(N, M / 2) + \Theta(N) = \underbrace{\Theta(N) + \dots + \Theta(N)}_{log(M)} = \Theta(NlogM) \]