open-courses
Search…
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