复习 笔记

数据结构与算法 期末复习笔记

时间不多了啊

Posted by Lin_Xuan on January 29, 2021

数据结构期末复习

以理论知识为主，插入少量核心代码/伪代码。重点复习ACM中不用/少用的部分，略过ACM中的常用算法，因此个人特点明显，不适合用来系统的复习/学习。

整体目录

[TOC]

参考知识点列表

参考知识点

复习中的不熟练、难点部分

  • 树、二叉树、森林的转换
  • AOE网络
  • B树、B+树、2-3树的插入与删除
  • 不同排序算法的稳定性分析

线性表

线性表的含义是指数据的逻辑关系是顺序的。但是根据数据在物理上的存储格式的不同，区分为顺序表和链表两种(链表有分为单链表、双链表、循环链表)。

链表的表头：链表根据是否带有表头可以分为两种。表头即作为链表头部的一个指针节点，但是并不储存数据，只是方便一些操作。

特殊的线性表：加入一些限制/功能，如队列、栈……

错题汇总

  • 链式储存所有的储存单元可连续可不连续(×)：节点内的储存单元必须连续

  • 在表元素序号的时候，一般从1开始。如插入第i个地方。

  • 给定n个元素的以一维数组，建立一个有序单链表的时间复杂度是____? $O(n^2)$,不可特殊化处理，链表的单次插入时$O(n)$。

  • 双向链表储存结构优点是？提高按关系查找元素的速度

  • 在单链表中，增加一个头节点的目的是？方便运算实现

  • 有n个元素，次序进栈，出栈序列有__种？$\frac{C_{2n}^{n}}{n+1}$种

  • 可以用两个栈模拟一个队列，但是不可以用两个队列模拟一个栈。
  • 链栈与顺序栈相比，有一个明显的有点，就是：通常不会出现栈满的操作
  • 可以用**数据元素**，**数据关系**，**基本操作**来定义一个抽象数据类型。

树结构

树

十分熟悉的数结构……在树结构中，节点的度的定义与图不同，此处定义外子节点的个数(树的度指树种节点的最大度数)。节点的深度定义为树种节点的最大层次，层次从0开始计，每向下层次+1(根为0)。树的高为最大层次再加一。

基本性质：

  • 度为m的树，第i层最多有$m^i$个节点。

  • 高度为h，度为m的树，最多有$\frac{m^{h-1}}{m+1}$个节点。

  • 有n个节点，度为m的树，最小高度为$\lceil log_m(n(m-1))+1\rceil$。

二叉树

完全二叉树是节点编号与同深度的满二叉树相同的二叉树。即满二叉树的条件更为苛刻。

对于度数为0或1的节点，通过增加空树叶的形式使得所有的节点度数为2(除了空树叶，度数为0)，叫做二叉树的扩充。外部路径和E指的是根节点到扩充后的二叉树的所有节点的路径长度的和。内部路径和E指根节点到扩充前的所有节点的路径和。有关系$E=i+2n$，n为二叉树不含空树叶的节点数量。

主要性质：

设终端节点/空节点的数量为$n_0$，度为1，2的节点的数量分别是$n_1,n_2$,节点总数为$n$。

  • $n_0=n_2+1$
  • 树的深度为$\lceil log_2(n+1)\rceil$。

二叉树的遍历形式有三种：前序、中序、后续，指的是根节点再遍历时的次序。又有递归和非递归两种实现方式。其中，后续的非递归形式最复杂，必须增加指针或其他信息来判断节点是否已经被访问过。

二叉搜索树(AVL树)

满足节点的左孩子比节点小，右孩子比节点大的二叉树。可以实现二分的插入与搜索。但是，单纯的不断插入会使得树的的深度增加的过于快，极端情况变成单支，影响算法的复杂度，因此可以通过各种方式来平衡化处理。常见的平衡树有AVL树。

AVL树增加平衡因子$bf(x)$，定义为左子树与右子树的高度差。平衡的二叉树平衡因子的取址应该是-1，0，1。

主要操作

AVL树主要通过“旋转操作”来维持平衡因子再取值范围内。有四种不平衡状态，对应有两种单旋转和两种双旋转两种情况。其中又有左右对称两种情况。


AVL树的四种不平衡情况

由于操作的对称性，只复习LL和LR两种不平衡的旋转方式。

单旋转：

LL和RR的情况需要做对称的单旋转处理。在图中的LL类型不平衡中，在左子树的左边插入1使得节点8的平衡因子变为-1，节点8失衡，因此针对节点8做右单旋处理。具体操作为：

  • 确定失衡节点k1和k1的左孩子k2
  • k1的左孩子指针指向k2的右孩子
  • k2的右孩子指针指向k1

这样操作，使得k2替代k1的位置，同时仍然满足二叉搜索树的性质(左孩子比节点小，有孩子比节点大。因为k1是大于k2的，因此k2称为根后k1只能称为k1的右孩子。而k2原本的右孩子则作为k1的左孩子(左孩子位置本来是k2,已经移走了))。

    void rote_with_left(AVLNode* &k1)
    {
        // 右旋(左支旋转)
        AVLNode* k2=k1->left_child;//这里不能用引用
        k1->left_child=k2->right_child;
        k2->right_child=k1;
        //不要忘记更新高度
        k1->height=max(k1->left_child->height,k1->right_child->height)+1;
        k2->height=max(k2->left_child->height,k2->right_child->height)+1;
        k1=k2;
    }

RR的操作与LL的操作对称，需要做左单旋。

双旋转：

针对LR和RL两种失衡，需要做两次单旋转，即双旋转才能恢复平衡。图中的LR失衡中，由于左子树的右子树插入5，使得节点8失衡。由于失衡位置在子树的右边，没办法通过一次旋转达到平衡，需要旋转两次，做左右双旋具体操作为：

  • k1仍为失衡节点，但是k2仍为k1的左节点。
  • 先以k2为失衡节点，做一次左单旋,再以k1为失衡节点，做一次对称的右单旋。

k2先进行一次左单旋后，平衡因子由原来的-1变为1，情况退化为LL的情况。那再做一次右单旋就解决问题了。

    void double_with_left(AVLNode* &k1)
    {
        // 左右双旋
        rote_with_right(k1->left_child);
        rote_with_left(k1);
    }

RL的操作与LR操作完全镜像。

插入：

插入时,采用递归的方法。在回退时判断节点是否失衡。一旦失衡，根据情况进行旋转纠正即可，代码相对比较容易。

删除：

删除的代码特别长……在这里理解一下原理，可以手动画出来算了……

删除有三种情况。依旧采用递归操作：

删除叶子节点：直接删除，递归地调整高度，在需要时做旋转操作。

删除节点只有左孩子/右孩子：直接删除，用左孩子/右孩子代替该节点，同时递归地调整高度，做旋转

删除既有左孩子又有右孩子的节点：找到节点的直接后继(也可以找前继)，替换该节点，同时删除直接后继。该操作可多次进行，最终回到前两种情况。(使用非递归的写法，会减少一点难度)

堆

堆是满足特殊性质的完全二叉树。堆满足根节点大于(小于)左右节点的大小。但是左右节点的相对大小不确定。根的常见用法是用来实现优先队列。

堆的性质主要依靠“上浮”和“下沉”两个操作来维护。

主要操作：

上浮

上浮。如果节点的值大于父亲节点的值，则交换节点与父亲节点，重复过程直到根节点。一般用在插入新数据时。

    void sift_up(size_t pos)
    {
        while(pos>1)
        {
            size_t parent=pos/2;
            if(cmp(array[parent],array[pos])==true)
                swap(array[pos],array[parent]);
            else 
                break;
            pos=parent;
        }
    }

下沉

将节点与左右孩子中较大的一个比较。(只需要同较大的比较，因为根只需要维持局部有序就可以了) 如果节点小于孩子节点，则交换两个的值。持续该过程直到叶子节点。一般用在删除数据后。

    void sift_down(size_t pos)
    {
        while(pos<=Capacity)
        {
            size_t child=pos<<1;
            if(child>Capacity) break;
            if(child+1<=Capacity and cmp(array[child],array[child+1])==true)
                child++;
            // child 要去left和right中较大的那个
            if(cmp(array[pos],array[child])){
                swap(array[pos],array[child]);
                pos=child;
            }
            else break;
        }
    }

插入和删除

插入元素时，将元素放到末尾，然后执行上浮操作。

删除元素一般为删除顶端节点，将元素删去，末尾的元素放置到该元素的位置，执行下沉操作。

初始化

有时候，或要求直接用数组生成一个堆。这是，倒叙遍历数组，执行下沉操作即可保证每棵子树都是堆。

Huffman 树

参考博客

霍夫曼树是用来编码和解码的。它用来找到一种对应关系，使得将文章编码以后所用的位数最少。同时字符的编码不会发生矛盾。

  1. 统计文章里每个字符出现的权重，选择权重最小的两个作为叶子节点，同时减权重列表里的两个权重删去，替换为两个权重，重复直至列表清空
  2. 从1中得到的根开始，给左节点赋值为0，右节点赋值为1，得到代表字符的叶子节点的二进制编码。

按照上述步骤，实际上树是从下往上生成的。最终列表内只剩一个元素，即树的根节点。同时，没有一个字符节点或作为其他字符节点大父节点(因为字符节点一定作为了叶子节点)。这样，就不有发生编码冲突。

树与森林

有多棵树既可以构成森林。

树、二叉树、森林的相互转换

建议手画一边，逻辑更清晰。

树->二叉树：

  1. 加线 。就是在所有兄弟结点之间加一条连线；
  2. 抹线。就是对树中的每个结点，只保留他与第一个孩子结点之间的连线，删除它与其它孩子结点之间的连线；
  3. 旋转。就是以树的根结点为轴心，将整棵树顺时针旋转一定角度，使之结构层次分明。

得到的二叉树都是单支的。并且，与右边的兄弟节点相连，则兄弟节点称为二叉树的右节点。

森林->二叉树

  1. 先把每棵树转换为二叉树；
  2. 第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子结点，用线连接起来。当所有的二叉树连接起来后得到的二叉树就是由森林转换得到的二叉树。

是指向相当于把根节点当作兄弟节点，也做了加线处理。

二叉树->树：

二叉树转换为树是树转换为二叉树的逆过程。

  1. 若某结点的左孩子结点存在，将左孩子结点的右孩子结点、右孩子结点的右孩子结点……都作为该结点的孩子结点，将该结点与这些右孩子结点用线连接起来；
  2. 删除原二叉树中所有结点与其右孩子结点的连线；
  3. 整理（1）和（2）两步得到的树，使之结构层次分明。

二叉树->森林：

  1. 先把每个结点与右孩子结点的连线删除，得到分离的二叉树；
  2. 把分离后的每棵二叉树转换为树；
  3. 整理第2步得到的树，使之规范，这样得到森林。

错题汇总

  • 高度为d的二叉树只有度为0和2的节点，则该二叉树的节点做少有( )个？2d-1个。高度为d，则至少有d-1个度为2的节点，同时又d个度为0的节点，总共2d-1。
  • 一课完全二叉树的第六层(根为第一层)有6个叶节点，则该二叉树最多又( )个节点？第六层又6个叶节点又两种情况，只放了六个叶节点/只有六个节点还是叶节点，因此最多111个。
  • 含有四个节点的二叉排序树的数目是( )？14！二叉排序树的中序遍历结果相同，先序不同，使用卡特兰数的公式计算可能数量为$\frac{C_{2n}^n}{n+1}$
  • 将森林转化成二叉树后，节点u是节点v双亲结点的双亲节点，则节点u和v在原来的森林中的关系是__?兄弟节点或父子节点

图论

图论中的度指的时与节点关联的边/弧的数目。不经过重复点的路径叫做简单路径，不经过重复边的路径叫做基本路径。

图论基础部分包括基本概念、存图的方式、图的DFS和BFS等。

最小生成树

两种算法，Kruskal直接排序、使用并查集判断，贪心的取边即可，复杂度与边的数量e有关。为$O(elog(e))$。Prim则维护其他节点到生成树集合的距离，使用优先队列维护，每次取最小，复杂度相对固定，只与点的数量有关，为$O(n^2)$。

最短路

Dijskra，单源最短路。每次用到源点u距离最短的点v取更新u到其他所有点的距离，需要重复n次。复杂度与查找距离u距离最短的点的方式有关。如果使用小根堆来维护，每次的代价是$log(n)$，总代价是$e(e+log(e))$。在稀疏图中更优秀(ACM比赛中受输入规模的限制，e不会太大。一般这种方法更优秀)。也可以直接取dis数组中找，这样复杂度是$O(n^2)$的(e最大可以是$n^2$的)。不能处理负权边。

Floyd算法，多源最短路。枚举以节点k为中转更新其他点之间的最短距离。$O(n^3)$。

SPFA，不稳定的单源最短路，与BFS接近，复杂度玄学。但是可以存在负权边。

AOE网络

拓扑序，按照入度排，不唯一。复杂度。

相关概念：

使用顶点表示事件、边表示活动的的有向图

每个事件代表它之前的活动已经完成、在它之后的活动可以开始。边权表示活动需要的时间。

关键路径：完成工程最短的时间是从源点到汇点的最长的路径长度。这条路径叫做关键路径。

event_earliest[vi]//事件vi最早的发生时间
event_latest[vi]//事件vi的最迟发生时间
activity_earliest[ai]//活动ai的最早发生时间
activity_latest[ai]//活动ai的最晚发生时间
dut[vi][vj]//活动ai的 持续时间,ai为vi->vj的关联事件

关键活动： activity_latest[ai]==activity_earliest[ai]的活动叫做关键活动。关键活动的完成情况是完成工程的效率关键。显然，关键路径上的活动都是关键活动。

算法思路：

设活动ai的前后时间分别为vj,vk，则有：

activity_earliest[ai]=event_earliest[vj];//最早的活动开始时间==活动前驱事件的最早达成时间
activity_latest[ai]=event_latest[vk]-det[vj][vk];//活动的最晚开始时间==后驱最晚达成时间-活动时间

设vi是vj的前驱事件(不唯一),则：

event_earliestv[vj]=max{event_earliest[vi]+dut[vi][vj]};//取最大，保障所有的前驱完成
event_latest[vi]=min{event_latest[vj]-dut[vi][vj]};//去任意值都能保证前驱、后驱完成，因此取最小
  1. 令event_earliest[v0]=0，正拓扑求event_earliest[vi]
  2. 令event_latest[vn]=event_earliest[vn]，逆拓扑求event_latest[vi]
  3. 根据公式求出所有的activity_earliest[ai]和activity_latest[ai]
  4. 找到activity_earliest[ai]==activity_latest[ai]的关键活动

错题汇总

暂无

排序

补充：基数排序

之前的理解有误，基数排序并不等同与桶排序。事实上，桶排序是基数排序选择大于所有数字的奇数时的情况。

基数排序的复杂度是$O(n*log(r)m)$，r为基数的大小，m为堆数。

以整数的排序为例子，由两种排序方法：LSD和MSD。

LSD

建立0~9的桶，首先按照个位数的顺序将元素放入桶中，再一次拿出，紧接着操作十位，百位……

那序列14, 22, 28, 39, 43, 55, 65, 73, 81, 93举例：

#第一次，个位
0
1 81
2 22
3 73 93 43
4 14
5 55 65
6
7
8 28
9 39

序列变为81, 22, 73, 93, 43, 14, 55, 65, 28, 39。紧接着操作第二位：

#第二次，十位
0
1 14
2 22 28
3 39
4 43
5 55
6 65
7 73
8 81
9 93

拿出来以后，得到递增序14, 22, 28, 39, 43, 55, 65, 73, 81, 93。首先从地位开始，是为了保证最后一轮放入桶中的元素，低位已经有序。

MSD

MSD更接近印象中的桶排序，采用分治的思路。它首先以最高位建桶，然后在每个桶内建立子桶……

经典排序算法。插入排序(直接插入、折半插入、Shell排序)，交换排序(冒泡排序、快速排序)，选择排序(直接选择，堆排序)和归并排序。

在排序中，排序算法的稳定性指排序后，原先在序列中相同大小的元素的前后位置会不会发生变化。不会发生变化则说明具有稳定性。反之则不稳定。

复杂度分析

直接插入排序：有序时最优$n-1$次比较，$2(n-1)$次移动，时间复杂度$O(n)$。反序时最坏，比较次数$\sum_1^{i-1}i=\frac{n(n-1)}{2}$，移动次数$\sum_1^{n-1}i+2=\frac{(n-1)(n+4)}{2}$，时间复杂度$O(n^2)$。

折半插入：减少了一些比较次数，但是总体复杂度和直接插入时一样的。

Shell排序：不稳定。玄学复杂度，介于$nlog(n)$和$n^2$之间。大概为$(O(n^{1.3}))$左右。

冒泡：最好情况比较次数为n-1(设置一个flag。如果在一次遍历中没有发生交换，则说明已经有序，直接返回。)，移动次数为0。最坏为$O(n^2)$。

以上的空间复杂度都是$O(1)$。

快速排序：不稳定。最好时是$O(nlog(n))$的。但是如果每次划分的区间有一个为空，则是$O(n^2)$的。空间上最好是$O(log(n))$，最坏是$O(n)$的。

直接选择排序：不稳定排序，不能保证相同元素的位置关系不变。但是性能稳定。$O(n^2)$次比较，$n-1$次移动。复杂度为确定的$O(n^2)$。空间复杂度$O(1)$。

堆排序：不稳定算法。时间复杂度为$nlog(n)$。空间复杂度$O(1)$。

归并排序：稳定算法。最坏时间复杂度为$O(nlog(n))$,空间复杂度为$O(n)$。但是比较次数较多，不一定比快速排序快。

排序算法的选择

时间优先选择：对元素个数较多的排序，可以选快速排序、堆排序、归并排序，元素个数较少时，可以选简单的排序方法。

空间优先选择：尽量选空间复杂度为O（1）的排序方法，其次选空间复杂度为O(log2n)的快速排序方法，最后才选空间复杂度为O（n）二路归并排序的排序方法。

一般选择方式：

  • 当待排序元素的个数n较大，排序码分布是随机，而对稳定性不做要求时，则采用快速排序为宜。
  • 当待排序元素的个数n大，内存空间允许，且要求排序稳定时，则采用二路归并排序为宜。
  • 当待排序元素的个数n大，排序码分布可能会出现正序或逆序的情形，且对稳定性不做要求时，则采用堆排序或二路归并排序为宜。
  • 当待排序元素的个数n小，元素基本有序或分布较随机，且要求稳定时，则采用直接插入排序为宜。
  • 当待排序元素的个数n小，对稳定性不做要求时，则采用直接选择排序为宜，若排序码不接近逆序，也可以采用直接插入排序。冒泡排序一般很少采用。
  • 稳定的排序方法有插入、折半、冒泡、归并四种。

错题汇总

  • 比较的次数与初始序列无关的算法是( )简单选择排序
  • 比较的趟数与初始序列无关的算法是( )直接插入、二路归并、简单选择、堆排序
  • 冒泡排序的趟数与初始序列有关。在某一趟中没有发生交换，就可以直接返回了。
  • 下列排序中，每次都能使一个元素到其最终位置上，并且时间性能收初始元素状态影响的算法是( 直接选择/直接插入/快排/堆排 )收初始状态影响的有快排、直接插入(直接插入有序是不需要移动)。但是只有快排每次可以使一个元素有序(选择的中间元素位置已经确定)

查找

主关键字：能够唯一的区分不同数据元素的关键字。

次关键字：不能唯一区分的关键字。

静态查找：只查找，不修改元素集合内的数据元素。

动态查找：既查找，也修改。

常见的静态查找有顺序查找，二分查找、分块查找。动态查找有B-树、2-3树(2阶B树)、B+树和散列查找。

评价查找算法的性能使用平均索引长度。集查找每个元素的概率与比较次数积的和。在散列查找中，有查找成功(查找的元素存在)的和查找失败的(查找的元素不存在)两种。

分块查找在主查找和二次查找都是用顺序查找的情况下，分块数目m与总元素数目满足$m=\sqrt{n}$时有最短平均查找长度。二分查找的平均查找长度为$log(N+1)-1$。

本章的重点放在动态查找的几种树的插入和删除上。

B-树

m阶B树：

  1. 每个节点至多有m个子树
  2. 根节点至少有两颗子树
  3. 除根节点意以外的非终端节点(叶子节点)至少有${\lceil\frac{m}{2}\rceil}$棵子树
  4. 有k个子节点的节点恰好包含k-1个关键码，区分k棵子树的数据范围。
  5. 所有的叶子节点在同一层

实例： 2-3树，三阶B树。下面以2-3树为例理解插入和删除操作。

在2-3树种，左子树的值小于第一个关键码，中间子树的值介于第一个关键码和第二个关键码之间。右子树的值大于关键码。注意，关键码同样也是待查找的储存的数据。只有一个关键码时，只有左子树和右子树。

插入：

新纪录会插入到叶子节点种。当叶子节点插入3个值的时候，就需要分裂提升操作(2阶b树每个节点最多2个记录),即中间值上升进入父节点，剩下两个值变成两颗父节点的两颗子树。如果父节点因为分裂提升拥有3个关键码，则继续向上分裂提升，直到树长高一层。因此，2-3树的增高是在根节点出发生的。

删除：

删除的类型很多。

  • 从包含两个记录的叶子节点删除：直接删除。
  • 从包含一个记录的叶子节点删除：向兄弟节点借一个值，同时修改双亲的记录。
  • 兄弟节点不够借的时候(双亲节点是3节点，即有三棵子树)：合并节点，影响双亲(从3节点变成2节点)
  • 兄弟节点不够借(双亲已经是2节点了)：合并相邻节点(最为复杂的一种情况)
  • 已经是满二叉树了：减少高度，合并相邻节点。

B+ 树

B树的一种变形。主要有几个点变化：

  • 所有的记录都出现在叶子节点上，根节点不在储存记录。根节点的关键码变成了下一层关键码的最大/最小关键码的复写。
  • 有k个子节点的节点必有k个关键码。

B+树的查找仍然是二分查找。但是在非叶子节点找到关键码是不停下，而是必须找到叶子节点上的关键码(因为删除的性质，内部节点的关键码可能已经被删掉了)

B+树的叶节点之间连接起来形成双链表，因此在顺序、范围检索上优势明显，实际应用种也是B+树较多。

插入：

与B树类似的分裂提升过程。注意上一层节点有这一层节点的最大关键码/最小关键码即可。

删除：

关键码不满时，与左右兄弟整合，过程类似B树。但是关键码在叶节点被删除后，上层的副本可以保留，作为分界存在。(因此查找时必须查找到叶子节点才行)

散列查找

散列函数

通过散列函数构造散列表，使用散列表(又称哈希表)进行元素的查找。散列表使用一个数组来储存每个插入的数据的位置，在访问时可以快速查找。理想的散列表插入和删除都是$O(1)$的。但是，$O(1)$的散列表空间复杂度极大，在实际应用中不可用。散列表的空间总大小为m，插入散列表的元素个数为n，ze称$a=\frac{n}{m}$为散列表的负载因子。

不同的数据储存在散列表的什么位置是由散列函数计算而来的。散列函数应该满足一些要求：

  1. 散列函数的定义域必须包含n，至于必须在$[0,m-1]$之间。
  2. 散列函数的计算结果越均匀越好
  3. 散列函数的计算过程不能太复杂。

常用的散列函数：

  1. 除留余数法：$H(key)=key\%p$
  2. 折叠法(移位法/分界法)： 如$key=381,412,975$,选取$H(key)=sum(key)\%1000$来取出后三位作为散列地址
  3. 平方取中法：将单个关键码平方，去中间的几位来作为散列地址
  4. 基数转换法：转化为其他进制来表示，再对表的大小取模
  5. 直接地址法：$H(key)=a\times key+b$

有人经过分析发现，平方取中法最接近随机化

解决冲突

有时候不同的数据会计算出相同的散列表位置，称为冲突。如何解决冲突是散列表的关键。

开散列： 散列表的每个位置对应一个链表，储存发生冲突的所有元素。查找时，先计算出散列地址，然后在链表种顺序查找。

开地址法(闭散列)

发生冲突时，通过移动储存的位置，占据散列表的其他位置来解决冲突。根据移动的方式问题，由不同的开地址方法。

线性探查：发生冲突时，顺序的向后移动寻找未使用的散列地址。

二次探查：构造两个散列函数。发生冲突时，使用第二个散列函数计算每次在散列表中每次移动的距离(地址对m取模)。第二个散列表的函数值要求取小于地址空间大小TableSize，且与TAbleSize互质的正整数。根据模数的性质，m次以内一定会回到源点，且散列表的所有位置都会遍历到。回到源点就说明散列表已满。

桶地址：散列表开成二维的，每个位置对应对各位置。储存满了以后再使用开地址法处理。

错题汇总

  • 不存在最好/坏的hash/散列函数，要视情况而定。
  • 散列查找的平均查找长度与集合中记录的元素的个数n无关。
  • 二分查找平均查找长度为$log(n+1)-1$，判定树的高度是$log(n+1)$，查找元素最多比较次数是$log(n)+1$。
CATALOG
    FEATURED TAGS
    复习 笔记 ACM 题解 Codeforces AtCoder
    FRIENDS