光阴冢 赛博空间的自留地

中位数和顺序统计

中位数和顺序统计学

最大值和最小值

应该很简单是 $\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)$。