# Algorithms and Computation

## Computation

Computation 中有三个重要概念，问题（Problem)、算法（Algorithm) 和效率（Efficiency）。这三个概念将永远伴随你走过计算机生涯。

### 问题

一个合法的**问题**有以下几个特点：

* 问题定义了从输入到正确输出的二元关系
* 通常问题描述不会穷举所有输入到所有正确输出的关系，而是提供一个可验证的方式来确定输出是否正确。
* 通常问题的输入有两种，有界和无界。无界的输入可以有无限种输入。

### 算法

一个合法的**算法**有以下几个特点：

* 算法是一个将输入映射到确定输出的过程
* ”一个算法解决了一个问题“，意思是对于问题的任意输入，该算法都能将其映射到正确的输出
* 算法的大小必须是有限的
* 算法必须要能证明它的正确性：
  * 有界输入问题：可以穷举
  * 无界输入问题：必须通过归纳法证明

### 效率

Asymptotic Notation:

* Upper Bounds: $$O$$ 
* Lower Bounds: $$Ω$$ 
* Tight Bounds: $$θ$$ 

| input | constant | logarithmic | linear   | log-linear  | quadratic  | polynomial | exponential             |
| ----- | -------- | ----------- | -------- | ----------- | ---------- | ---------- | ----------------------- |
| n     | $$θ(1)$$ | $$θ(lgn)$$  | $$θ(n)$$ | $$θ(nlgn)$$ | $$θ(n^2)$$ | $$θ(n^c)$$ | $$2^{θ(n^c)}$$          |
| 1000  | 1        | $$≈ 10$$    | 1000     | $$≈ 10000$$ | 1000000    | ...        | $$2^{1000} ≈ 10^{301}$$ |

在谈论算法效率之前，必须明确我们的计算模型（Model of Computation）是什么：

#### Word-RAM

内存可以理解成可随机访问的数组，每个元素是一个字（32-bit 或者 64-bit），每次随机访问的时间复杂度为 $$O(1)$$ 

## 如何用算法解决一个问题

### Reduce

将其转化成你所熟知的数据结构及算法，如：

#### Search Data Structures

* Array
* Sorted Array
* Linked List
* Dynamic Array
* Binary Heap
* Binary Search Tree / AVL
* Direct-Access Array
* Hash Table

#### Sort Algorithms

* Insertion Sort
* Selection Sort
* Merge Sort
* Heap Sort
* AVL Sort
* Counting Sort
* Radix Sort

#### Shortest Path Algorithms

* Breadth First Search
* Depth First Search/Topo. Sort
* Dijkstra
* Bellman-Ford
* Floyd-Warshall
* Johnson

...

### Design

设计你的递归/迭代算法：

* 将函数调用抽象成计算图中的一个点，A -> B 表示 A 调用 B
* 将算法按照计算图进行归类，见下表
* 证明算法的正确性

| 算法类别                 | 计算图类别 | 访问节点数量 |
| -------------------- | ----- | ------ |
| Brute Force          | Star  | All    |
| Decrease & Conquer   | Chain | All    |
| Divide & Conquer     | Tree  | All    |
| Dynamic Programming  | DAG   | All    |
| Greedy / Incremental | DAG   | Some   |


---

# 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/algorithms-and-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.