Chapter4 数据结构和算法概述

说明

这部分要开始用中文了，用英文做笔记实在是太费劲了

时间复杂度分析¶

$O(),\Theta(),\Omega()$复杂度¶

$O()$ 表示函数的上界，描述函数在最坏情况下的增长率不超过某个函数的增长率，其数学定义如下：

对于函数 $f(n)$ 和 $g(n)$，如果存在正实数常数 $c$ 和 $n_0$，使得对于所有 $n\geq n_0$，有： $$ f(n)\leq c\cdot g(n) $$ 我们就称 $f(n) \in O(g(n))$，表示 $f(n)$ 的增长率小于或等于 $g(n)$ 的增长率

$\Theta()$ 表示函数的精确增长阶，描述函数的增长率和某个函数的增长率在渐进意义下相等（既是上界也是下界），其数学定义如下：

对于函数 $f(n)$ 和 $g(n)$，如果存在正实数常数 $c_1,c_2$ 和 $n_0$，使得对于所有 $n\geq n_0$，有： $$ c_1\cdot g(n)\leq f(n)\leq c_2\cdot g(n) $$ 我们就称 $f(n)\in \Theta(g(n))$，表示 $f(n)$ 的增长率与 $g(n)$ 在同一量级

$\Omega()$ 表示函数的下界，描述函数的增长率不低于某个函数的增长率，其数学定义如下：

对于函数 $f(n)$ 和 $g(n)$，如果存在正实数常数 $c$ 和 $n_0$，使得对于所有 $n\geq n_0$，有： $$ f(n)\geq c\cdot g(n) $$ 我们就称 $f(n)\in \Omega(g(n))$，表示 $f(n)$ 的增长率大于或等于 $g(n)$ 的增长率

注意

需要说明的是，$O()$ 并不等同于“最坏情况”，其关注最坏情况的上限；同样 $\Omega()$ 也不等同于最佳情况，其关注最优情况的下限，但它们经常被这样使用了，$O()$ 有以下几个应用场景：

它允许我们在不同输入、运行时间不同的情况下，做出简单的陈述，而无需考虑具体情况
有时我们可能不知道确切的运行时间，因此我们只能给出一个上界
$\Theta()$ 提供了最精确的描述，但是我们也同时需要证明上界和下界，而证明 $O()$ 比证明 $\Theta()$ 容易得多。

均摊分析(Amortized Analysis)¶

均摊分析是一种分析算法运行时间的方法，特别适用于某些操作成本高但发生频率低的情况，它的目标是计算一系列操作的平均成本（即使某些操作的成本可能远高于其他操作）。

下面我们来看一个直观的例子—— Grigometh 干草问题

Grigometh 是一只恶魔犬，它赋予你让马在梦中显现的能力，但是你必须定期向它提供一罐罐干草作为贡品，他给了你两种方案：

每天3罐
按2的幂次提供干草，且频率逐渐降低，第1天1罐，第2天2罐，第4天四罐，第8天8罐，以此类推。

下面我们计算一下第二种方法均摊下来每天的贡品数量，在第 $2^n$ 天时，总共上贡的罐数为： $$ 1+2+2^2+\cdots+2^n=\frac{1(1-2^{n+1})}{1-2}=2^{n+1}-1 $$ 而均摊到这 $2^n$ 天可以得到 $$ \frac{2^{n+1}-1}{2^{n}}<2 $$ 所以方案2的均摊成本实际上比方案1更优

抽象数据类型(The Abstract Data Type)¶

抽象数据类型（ADT）是由其行为定义的高级类型，而非由其实现定义的。比如在 CS61B 课程的 Proj1 ，我们所实现的 Deque 双端队列是一个具有某些行为（比如 addFirst,addLast）等的 ADT，但是我们实际用来实现它的数据结构是 ArrayDeque 和 LinkedListDeque。一些抽象数据类型其实是其他抽象数据类型的特殊情况，比如栈和队列只是具有更具体的行为的列表。

ADT 与其接口(interface)相关，接口定义了 ADT 的行为，而具体类则通过继承接口实现这些操作。

常见ADT及其操作¶

Stacks（栈）：后进先出
- push(int x)：将元素 x 放入栈顶
- int pop()：移除并返回栈顶元素
Lists（列表）： 有序元素集合
- add(int i)：添加元素
- int get(int i)：获取索引 i 处的元素
Sets（集合）：无序、唯一元素的集合（不重复）
- add(int i)：添加元素
- contains(int i)：检查是否包含某个元素
Maps（映射）：键值对集合
- put(K key, V value)：添加键值对
- V get(K key)：获取键对应的值

Stacks、Lists、Sets、Maps是 Collections 接口的子接口