# 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](/files/-LSIkliUSzc6IR2OSFFD)

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

![图 2 - 计算图 B](/files/-LSIleidAlB8Ig3dVP_L)

现在问题变得更容易了，图 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
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://zhenghe.gitbook.io/open-courses/mit-6.006/structure-of-computation.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.