穹苍之上，一片寂寥，群星慢慢地闭上了眼睛。
计算模型
什么是算法
- 算法是解决问题的计算步骤：通过对输入进行处理，得到输出。
- 算法是对于程序的数学化分析
下面我们构造一个实际程序和算法的对应模型：
什么是计算模型
计算模型决定以下两点：
- 算法能执行哪些操作
- 每一个操作的代价（时间、空间）是怎样的，这里我们重点关注时间
不同的计算模型
随机存取机（Random access machine, RAM）
记得和随机存储器进行区分，这里的随机存储机是一种计算模型，它有如下特点：
- $\Theta(1)$的寄存器读取和写入一个word
- 可以进行$\Theta(1)$时间的计算
RAM的可视化表示如下图所示：
那么这里的word是什么呢？是64位还是32位？这里其实是一个抽象的大小，我们令其为$w$ size，其中$w\ge \lg(\mathrm{memory\ size})$，确保可以在内存空间中确定其位置。我们这里不考虑大数问题，即word长度很长的问题。我们常用的vector就是一个随机存取机下的模型。
指针机（pointer machine）
- 动态分配对象
- 对象拥有$\Theta(1)$的区域（字段）
- 一个区域（字段）可以为：
- 一个word（例如一个
int） - 一个指向另一个对象的或者为空的指针
- 一个word（例如一个
我们常用的list就是一个指针机下的一个模型，当然，也可以用RAM实现一个list，此时list的指针就成了内存中的某个位置的索引，指向下一个节点。Pointer机的示意图如下：
Python实现
python下RAM的数据结构为list，一些操作的时间复杂度如下：
- append：$\Theta(1)$时间复杂度
- 连接字符串：$\Theta(l_1)+\Theta(l_2)=\Theta(l_1+l_2)$
- 查找：$\Theta(n)$
- 排序：$\Theta(n\lg n)$
python下的大数为long，假设两个操作数长度为$x$和$y$，一些操作的时间复杂度如下：
- $x+y$：$\Theta(x+y)$
- $x\times y$：$\Theta(x+y)^{\lg 3}$
文本距离问题
定义
文本距离问题定义为，给定两个文本$D_1$和$D_2$，求两个文本之间的距离$d(D_1,D_2)$或者说相似度。这个很常用，例如搜索引擎，或者文本查重等。其中文本的定义即为一个单词（word）序列，而一个单词即若干字母的组合（char）。
计算方法
方法一：使用内积定义相似度
一个简单的思路是考虑相同的words在两个文本中出现的次数，令$D[w]$为单词$w$在$D$中出现的次数，$D[w]$为非负整数。给定$D_1,D_2$如下：
那么可以画出如下坐标系
实际上，我们可以将一个文本$D$视为单词空间中的一个向量，单词空间中每一个单词即为一个空间中一个维度，那么我们计算两个向量的距离实际上就是求内积的过程，当两个文本完全相同，其内积达到最大，说明相似度最高：
缺陷
这个问题的缺陷在于，这个距离并不能实质性反映出文本间差异的大小，例如我有两个文本，都是百万量级的长度，其中有百分之50的单词相同，那么两个文本间的内积可能非常大；而另外两个文本长度为100，且长度均相同，但是内积反而没有前面的文本大。但实际上第二种情况的文本相似程度应当比第一个大。
方法二：使用向量夹角定义内积相似度
我们对方法一进行改进，使用两个文本向量的夹角定义相似度，那么得到的距离为：
如果夹角为0，那么很相似；如果夹角为180，说明根本不相似。
算法
我们根据方法二，写一下文本距离的算法：
- 将文本分割为独立的单词：线性时间
- 计算单词频率：线性时间
- 进行内积，求夹角
课程中提供了8种算法，针对一个大型的文本，其处理时间分别为：
- 228.1秒
- 164.7秒
- 123.1秒
- 71.7秒
- 18.3秒
- 11.5秒
- 1.8秒
- 0.2秒