算法#

算法是对解决问题的方法的描述.

算法可以简单地被分成3个抽象等级.

计算模型#

计算模型包括:

1. 算法实现允许直接使用的底层运算(比如CPU内置了加法器和乘法器, 对应加法和乘法)
2. 单个运算的开销(时间和空间)
3. 算法的开销(等同于运算数量*单个运算的开销)

随机访问机模型(random access machine)#

与内存random access memory区分, 随机访问机是内存的数学抽象.

简单来说, 回顾算法中的表格, 内存属于计算机底层, 而随机访问机属于计算模型, 与内存相对应.

相当于一个储存字(word) ¹的巨型数组, .

具有O(1)的如下操作:

1. 读取O(1)数量的字
2. 做O(1)数量的算术和逻辑运算
3. 存储O(1)数量的字

(与寄存器进行交互)

指针模型(pointer machine)#

相对于随机访问机模型而言, 抽象程度更高(就是说, 更方便使用).

相当于一个动态数组, 具有a(任意)个对象.

每个对象包含O(1)个字段.

每个字段可能是一个字或者一个指针(引用).

解释

这个概念很抽象. 如果学过C++的话可以想象一个巨大的std::vector, 每个格子储存一个结构体, 每个结构体包含若干个常规数据(int, char等), 或者一个指针(指向另一个int, char 甚至 另一个结构体). 这里的结构体就对应pointer machine中的对象. 常规数据或者指针就对应一个字段. 比如可以用pointer machine解释链表. 一个节点相当于一个对象. 每个对象里包含三个字段: val用来存储值, prev指向前一个节点, next指向后一个节点.

python的计算模型#

说实话这节我根本没看懂. 大概思想就是python中既存在随机访问机模型(list), 也存在指针模型(object). 这可以使我们常见的操作(索引访问, 指针访问, append等)在O(1)内完成.

若L1和L2是两个列表, x, y是整数(大整数), D是一个字典:

1
L1.append(x)    # O(1)
2
L = L1 + L2     # O(|L1| + |L2|)
3
x in L          # O(|L|)
4
len(L)          # O(1)
5
L.sort()        # O(|L|log|L|)
6
D[key]          # O(1)
7
key in D        # 平均略大于O(1)
8
x + y           # O(|x|+|y|)
9
x * y           # O((|x|+|y|)^1.6)