中位数和顺序统计学

最大值和最小值

应该很简单是 $\Theta(n)$ 的复杂度。

1. 最大或最小 直接遍历就可以了。

2. 最大和最小 普遍的方法是执行 2 遍上一过程。对规模为 n 的输入来说，至多比较 $2n -2$ 次。

   但实际上也有更好的办法，比较 $3\lfloor n / 2 \rfloor$ 次。 成对处理数据，先将一对数据进行比较，将大的和现在的最大值进行比较，小的和现在的最小值进行比较。 这样，每对数据需比较 3 次。

选择问题

1. 期望为 $\Theta(n)$ 的随机选择 感觉确实之前想不到这样的办法。=_= 本质也是划分大问题为小问题。用随机的主元元素将数组划分，计算比主元大的数目，如果比 i 大的话就在划分高区再找，比 i 小的话则在另一个里面。

2. 最坏为 $\Theta(n)$ 选择算法

   1. 将输入数组的 n 个元素划分为 $\lceil n / 5 \rceil$ ，仅有一组可能不是 5 个元素。
   2. 寻找每一组的中位数，排序后选择即可。
   3. 递归调用自己，找到所有中位数的下中位数 $x$。
   4. 将下中位数作为主元进行划分。
   5. 判断并分区递归寻找。

   这个被证明是最坏 $\Theta(n)$ ，直觉上有点不能理解为什么是 5 不是其他数字。如果是 3 或者 7 呢？

数据结构

很多以前学过的就不写了。

散列表(Hash Table)

• 散列表 尽可能达到 $O(1)$ 的时间复杂度。

• 散列函数

  1. 乘法散列 $$ h(k) = \lfloor m(k A \mod 1) \rfloor $$
  2. 全域散列 设 $ H $ 为有限的一组散列函数，它将给定的关键字域 $U$ 映射到 $ { 0, 1, ···, m-1 } $ 中。 这样的函数族称为是全域的，如果对每一对不同的关键字 $k,l \in U$ ，满足 $h(k) = h(l)$ 的散列函数 $ h \in H $ 的个数至多为 $|H| / m$ 。

• 开放寻址法

  • 特性

    不使用链表形式存储，所有的值(或者值的指针)都在同一散列表里。查找的时候必须按照当时插入的时候的算法进行逐个查看，直到值为空时再判断是否没有。 但是在执行删除操作时，不能仅将当时的位置的值设为 NUL，否则会出现之后的值都无法被检索的错误。 解决方法是在这个地方插入一个特殊的 DELETED 的值。同时，查找时间就不再依赖于装载因子 $alpha$ 了。 因此在必须存在删除操作的散列表中，一般使用链接法来解决碰撞。

  • 计算探查序列

    1. 线性探查 依次线性查找。 可能会出现一次群集的现象。导致连续占用的槽不断增加。

    2. 二次探查 偏移量为二次函数。

    3. 双重散列 偏移量由另一个散列函数决定。

• 完全散列

  • 性质 当关键词集合是静态的时候，可以达到相当好的最坏情况性能($O(1)$)。

  • 基本想法 利用一种两级的散列方案，每一级都使用全域散列。确保二次散列表中不出现碰撞，且总存储空间为 $O(n)$。