Structure Of Computation

回顾：如何解决一个算法问题

• Reduce：将问题转化成你熟悉的数据结构及算法

• Design：根据计算图设计某种递归/迭代算法。不同计算图所采用的解法不同，解法可以分为以下几个类别：Brute Force、Decrease & Conquer、Divide & Conquer、Dynamic Programming 和 Greedy / Incremental

问题及解决方法举例

Contains

• Problem：给定一个包含 n 个整数的数组 A，判断它是否包含整数 v

• Example:

  • input: $A = [1, 2, 3, 4, 5], v = 3$

  • output: true

Brute Force $O(n)$

def contains(A, v):
    for i in range(len(A)):
        if A[i] == v: return True
    return False

Decrease & Conquer $O(n)$

def contains(A, v, i=0):
    if i >= len(A) or i < 0:
        return False
    if A[i] == v:
        return True
    return contains(A, v, i+1)

Divide & Conquer $O(n)$

def contains(A, v, i=0, j=None):
    if j is None:
        j = len(A)
    if j - i == 0:
        return False
    c = (i+j) // 2
    if A[c] == v:
        return True
    return contains(A, v, i, c) or contains(A, v, c+1, j)

Greedy, if sorted A $O(logn)$

def contains(A, v, i=0, j=None):
    if j is None:
        j = len(A)
    if j - i == 0:
        return False
    c = (i+j) // 2
    if A[c] == v:
        return True
    elif A[c] > v:
        return contains(A, v, i, c)
    else:
        return contains(A, v, c+1, j)

Max Subarray Sum

• Problem: 给定一个长度为 n 的整数数组 A，找到和最大的子数组

• Example:

  • Input: $A = [-9, 1, -5, 4, 3, -6, 7, 8, -2]$
  • output: 16

Brute Force $O(n^3)$

遍历所有可能的子数组：

• 长度 = 1 的子数组 ${n}\choose{1}$ ，长度 > 1 的子数组 ${n}\choose{2}$ ，总数为 $O(n^2)$
• 对长度为 k 的子数组求和，时间复杂度为 $O(k)$
• 总体时间复杂度为 $O(n^3)$

def MSS(A):
    m = A[0]
    for j in range(1, len(A)+1):
        for i in range(0, j):
            m = max(m, SS(A, i, j))
    return m

def SS(A, i, j):
    s = 0
    for k in range(i, j):
        s += A[k]
    return s

Divide & Conquer $O(nlogn)$

• 最大子数组有三种可能：整体位于左半边、整体位于右半边，横跨左右半边

• 计算图为树形

• $T(n) = 2T(n/2) + O(n) => T(n) = O(nlogn)$

def MSS(A, i=0, j=None):
    if j is None:
        j = len(A)
    if j - i == 1:
        return A[i]
    c = (i+j)//2
    return max(MSS(A, i, c), 
               MSS(A, c, j),
               MSS_EA(A, i, c) + MSS_SA(A, c, j))
  
def MSS_SA(A, i, j):
    s = m = A[i]
    for k in range(1, j-i):
        s += A[i+k]
        m = max(s, m)
    return m

def MSS_EA(A, i, j):
    s = m = A[j-1]
    for k in range(1, j-i):
        s += A[j-1-k]
        m = max(s, m)
    return m

Dynamic Programming

如果$MSS\_EA(A, 0, k)$ 表示 A 中以第 k 个元素结尾的子数组，以下简称 $(A, 0, k)$ ，问题就按如下方式解决：

def MSS(A):
    m = A[0]
    for k in range(len(A)):
        s = MSS_EA(A, 0, k+1)
        m = max(m, s)
    return m

但 MSS_EA 的时间复杂度为 $O(n^2)$ ，总体时间复杂度就与暴力解法如出一辙。但我们仔细思考，可以发现该过程中存在着重复计算：

图 1 - 计算图 A

如图 1 所示，在计算和最大的子数组过程中，重复计算了 n 次 $(A, 0, 0)$ ，n-1 次 $(A, 0, 1)$，...重新整理一下计算图，可以得到：

图 2 - 计算图 B

现在问题变得更容易了，图 B 中只有 n 个节点，且是一个有向无环图（DAG），恰好该图的拓扑排序正好是从 0 到 n，因此可以得到如下算法：

def MSS(A):
    m = mss_ea = A[0]
    for i in range(1, len(A)):
        mss_ea = A[i] + max(0, mss_ea)
        m = max(m, mss_ea)
    return m