# 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)$$ 

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

#### Decrease & Conquer $$O(n)$$ 

```python
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)$$&#x20;

```python
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)$$&#x20;

```python
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]$$&#x20;
  * output: 16

#### Brute Force $$O(n^3)$$&#x20;

遍历所有可能的子数组：

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

```python
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)$$&#x20;

* 最大子数组有三种可能：整体位于左半边、整体位于右半边，横跨左右半边
* 计算图为树形
* $$T(n) = 2T(n/2) + O(n)  => T(n) = O(nlogn)$$&#x20;

```python
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)$$ ，问题就按如下方式解决：

```python
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](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LSIbow8lpd8tVyTlpJP%2F-LSIkliUSzc6IR2OSFFD%2FScreen%20Shot%202018-11-27%20at%202.02.16%20PM.jpg?alt=media\&token=bf8fdcd0-a0ff-4ccd-b5e1-8fae5ab89e5a)

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

![图 2 - 计算图 B](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LSIbow8lpd8tVyTlpJP%2F-LSIleidAlB8Ig3dVP_L%2FScreen%20Shot%202018-11-27%20at%202.06.17%20PM.jpg?alt=media\&token=d79217d4-f163-4082-81dd-d84efca6fa34)

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

```python
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
```