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=3A = [1, 2, 3, 4, 5], v = 3

    • output: true

Brute Force O(n)O(n)

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

Decrease & Conquer O(n)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)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)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]A = [-9, 1, -5, 4, 3, -6, 7, 8, -2]

    • output: 16

Brute Force O(n3)O(n^3)

遍历所有可能的子数组:

  • 长度 = 1 的子数组 (n1){n}\choose{1} ,长度 > 1 的子数组 (n2){n}\choose{2} ,总数为 O(n2)O(n^2)

  • 对长度为 k 的子数组求和,时间复杂度为 O(k)O(k)

  • 总体时间复杂度为 O(n3)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)O(nlogn)

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

  • 计算图为树形

  • T(n)=2T(n/2)+O(n)=>T(n)=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)MSS\_EA(A, 0, k) 表示 A 中以第 k 个元素结尾的子数组,以下简称 (A,0,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(n2)O(n^2) ,总体时间复杂度就与暴力解法如出一辙。但我们仔细思考,可以发现该过程中存在着重复计算:

图 1 - 计算图 A

如图 1 所示,在计算和最大的子数组过程中,重复计算了 n 次 (A,0,0)(A, 0, 0) ,n-1 次 (A,0,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