notes

This site uses Just the Docs, a documentation theme for Jekyll.

数据结构

一些概念

线性表

线性表是一种典型的线性结构。头结点无前驱有一个后继，尾节点无后继有一个前驱。链表只能顺序查找，定位一个元素的时间为 O(N)，删除一个元素的时间为 O(1)

  1. 线性表的顺序存储结构：把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。是一种随机存取的存储结构。顺序存储指内存地址是一块的，随机存取指访问时可以按下标随机访问，存储和存取是不一样的。如果是存储，则是指按顺序的，如果是存取，则是可以随机的，可以利用元素下标进行。数组比线性表速度更快的是：原地逆序、返回中间节点、选择随机节点。

    • 便于线性表的构造和任意元素的访问
    • 插入：插入新结点，之后结点后移。平均时间复杂度: O(n)
    • 删除：删除节点，之后结点前移。平均时间复杂度: O(n)

  2. 线性链表：用一组任意的存储单元来依次存放线性表的结点，这组存储单元即可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。因此，链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址。data 域是数据域，用来存放结点的值。next 是指针域（亦称链域），用来存放结点的直接后继的地址（或位置）。不需要事先估计存储空间大小。

    • 单链表中每个结点的存储地址是存放在其前趋结点 next 域中，而开始结点无前趋，故应设头指针 head 指向开始结点。同时，由于最后一个结点无后继，故结点的指针域为空，即 NULL。头插法建表 (逆序)、尾插法建表 (顺序)。增加头结点的目的是算法实现上的方便，但增大了内存开销。

      • 查找：只能从链表的头指针出发，顺链域 next 逐个结点往下搜索，直到搜索到第 i 个结点为止。因此，链表不是随机存取结构。
      • 插入：先找到表的第 i-1 的存储位置，然后插入。新结点先连后继，再连前驱。
      • 删除：首先找到 a[i-1] 的存储位置 p。然后令 p–>next 指向 a[i] 的直接后继结点，即把 ai 从链上摘下。最后释放结点 ai 的空间. r=p->next;p->next=r->next;delete r。
      • 判断一个单向链表中是否存在环的最佳方法是快慢指针。
    • 静态链表：用一维数组来实现线性链表，这种用一维数组表示的线性链表，称为静态链表。静态：体现在表的容量是一定的。（数组的大小）；链表：插入与删除同前面所述的动态链表方法相同。静态链表中指针表示的是下一元素在数组中的位置。
    • 静态链表是用数组实现的，是顺序的存储结构，在物理地址上是连续的，而且需要预先分配大小。动态链表是用申请内存函数（C 是 malloc,C++ 是 new）动态申请内存的，所以在链表的长度上没有限制。动态链表因为是动态申请内存的，所以每个节点的物理地址不连续，要通过指针来顺序访问。静态链表在插入、删除时也是通过修改指针域来实现的，与动态链表没有什么分别

    • 循环链表：是一种头尾相接的链表。其特点是无须增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活。

      • 在单链表中，将终端结点的指针域 NULL 改为指向表头结点的或开始结点，就得到了单链形式的循环链表，并简单称为单循环链表。由于循环链表中没有 NULL 指针，故涉及遍历操作时，其终止条件就不再像非循环链表那样判断 p 或 p—>next 是否为空，而是判断它们是否等于某一指定指针，如头指针或尾指针等。

    • 双向链表: 在单链表的每个结点里再增加一个指向其直接前趋的指针域 prior。这样就形成的链表中有两个方向不同的链。双链表一般由头指针唯一确定的，将头结点和尾结点链接起来构成循环链表，并称之为双向链表。设指针 p 指向某一结点，则双向链表结构的对称性可用下式描述：p—>prior—>next=p=p—>next—>prior。从两个方向搜索双链表，比从一个方向搜索双链表的方差要小。

      • 插入：先搞定插入节点的前驱和后继，再搞定后结点的前驱，最后搞定前结点的后继。
      • 在有序双向链表中定位删除一个元素的平均时间复杂度为 O(n)
      • 可以直接删除当前指针所指向的节点。而不需要像单向链表中，删除一个元素必须找到其前驱。因此在插入数据时，单向链表和双向链表操作复杂度相同，而删除数据时，双向链表的性能优于单向链表

栈和队列

队列

串

串 (String) 是零个或多个字符组成的有限序列。长度为零的串称为空串 (Empty String)，它不包含任何字符。通常将仅由一个或多个空格组成的串称为空白串 (Blank String) 注意：空串和空白串的不同，例如 “ ” 和“”分别表示长度为 1 的空白串和长度为 0 的空串。

串的表示和实现：

  1. 定长顺序存储表示。静态存储分配的顺序表。
  2. 堆分配存储表示。存储空间是在程序执行过程中动态分配而得。所以也称为动态存储分配的顺序表
  3. 串的链式存储结构。

串匹配：将主串称为目标串，子串称之为模式串。蛮力法匹配。KMP 算法匹配。Boyer-Moore 算法匹配。

数组和广义表

树和二叉树

图

查找

顺序查找、折半查找、索引查找、分块查找是静态查找，动态查找有二叉排序树查找，最优二叉树查找，键树查找，哈希表查找

静态查找表

顺序表的顺序查找：应用范围：顺序表或线性链表表示的表，表内元素之间无序。查找过程：从表的一端开始逐个进行记录的关键字和给定值的比较。

顺序有序表的二分查找。平均查找时间 (n+1)/n log2(n+1)

分块查找：将表分成几块，块内无序，块间有序，即前一块中的最大值小于后一块中的最小值。并且有一张索引表，每一项存放每一块的最大值和指向该块第一个元素的指针。索引表有序，块内无序。所以，块间查找用二分查找，块内用顺序查找，效率介于顺序和二分之间；先确定待查记录所在块，再在块内查找。因此跟表中元素个数和块中元素个数都有关。

  1. 用数组存放待查记录,
  2. 建立索引表，由每块中最大（小）的关键字及所属块位置的信息组成。
  3. 当索引表较大时，可以采用二分查找
  4. 在数据量极大时，索引可能很多，可考虑建立索引表的索引，即二级索引，原则上索引不超过三级

分块查找平均查找长度：ASLbs = Lb + Lw。其中，Lb 是查找索引表确定所在块的平均查找长度， Lw 是在块中查找元素的平均查找长度。在 n 一定时，可以通过选择 s 使 ASL 尽可能小。当 s=sqrt(n) 时，ASL 最小。

  1. 时间：顺序查找最差，二分最好，分块介于两者之间
  2. 空间：分块最大，需要增加索引数据的空间
  3. 顺序查找对表没有特殊要求
  4. 分块时数据块之间在物理上可不连续。所以可以达到插入、删除数据只涉及对应的块；另外，增加了索引的维护。
  5. 二分查找要求表有序，所以若表的元素的插入与删除很频繁，维持表有序的工作量极大。
  6. 在表不大时，一般直接使用顺序查找。

动态查找

二叉排序树的结点删除：

  1. x 为叶子结点，则直接删除
  2. x 只有左子树 xL 或只有右子树 xR , 则令 xL 或 xR 直接成为双亲结点 f 的子树；
  3. x 即有左子树 xL 也有右子树 xR，在 xL 中选值最大的代替 x，该数据按二叉排序树的性质应在最右边。

平衡二叉树：每个结点的平衡因子都为 1、－1、0 的二叉排序树。或者说每个结点的左右子树的高度最多差 1 的二叉排序树。

平衡二叉树的平衡：

  1. 左调整 (新结点插入在左子树上的调整)：

    • LL(插入在结点左子树的左子树上)：旋转前后高度都为 h+1
    • LR(新插入结点在左子树的右子树上)：旋转前后高度仍为 h+1

  2. 右调整 (新结点插入在右子树上进行的调整):

    • RR(插入在的右子树的右子树上)：处理方法和 LL 对称
    • RL(插入在的右子树的左子树上)：处理方法和 LR 对称

平衡树建立方法：

  1. 按二叉排序树插入结点
  2. 如引起结点平衡因子变为 2 ，则确定旋转点，该点是离根最远（或最接近于叶子的点）
  3. 确定平衡类型后进行平衡处理，平衡后以平衡点为根的子树高不变
  4. 最小二叉平衡树的节点的公式如下 F(n)=F(n-1)+F(n-2)+1 这个类似于一个递归的数列，可以参考 Fibonacci 数列，1 是根节点，F(n-1) 是左子树的节点数量，F(n-2) 是右子树的节点数量。

常见的平衡二叉树：

  1. 红黑树是平衡二叉树，也就是左右子树是平衡的，高度大概相等。这种情况等价于一块完全二叉树的高度，查找的时间复杂度是树的高度，为 logn，插入操作的平均时间复杂度为 O(logn)，最坏时间复杂度为 O(logn) /assets/404.png

    • 节点是红色或黑色。
    • 根是黑色。
    • 所有叶子都是黑色（叶子是 NIL 节点）。
    • 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
    • 从任一节点到其每个叶子的所有简单路径 都包含相同数目的黑色节点。
  2. avl 树也是自平衡二叉树；红黑树和 AVL 树查找、插入、删除的时间复杂度相同；包含 n 个内部结点的红黑树的高度是 o(logn); TreeMap 是一个红黑树的实现，能保证插入的值保证排序

  3. STL 和 linux 多使用红黑树作为平衡树的实现：

    1. 如果插入一个 node 引起了树的不平衡，AVL 和 RB-Tree 都是最多只需要 2 次旋转操作，即两者都是 O(1)；但是在删除 node 引起树的不平衡时，最坏情况下，AVL 需要维护从被删 node 到 root 这条路径上所有 node 的平衡性，因此需要旋转的量级 O(logN)，而 RB-Tree 最多只需 3 次旋转，只需要 O(1) 的复杂度。
    2. 其次，AVL 的结构相较 RB-Tree 来说更为平衡，在插入和删除 node 更容易引起 Tree 的 unbalance，因此在大量数据需要插入或者删除时，AVL 需要 rebalance 的频率会更高。因此，RB-Tree 在需要大量插入和删除 node 的场景下，效率更高。自然，由于 AVL 高度平衡，因此 AVL 的 search 效率更高。
    3. map 的实现只是折衷了两者在 search、insert 以及 delete 下的效率。总体来说，RB-tree 的统计性能是高于 AVL 的。

查找总结

  1. 既希望较快的查找又便于线性表动态变化的查找方法是哈希法查找。二叉排序树查找，最优二叉树查找，键树查找，哈希法查找是动态查找。分块、顺序、折半、索引顺序查找均为静态。分块法应该是将整个线性表分成若干块进行保存，若动态变化则可以添加在表的尾部（非顺序结构），时间复杂度是 O(1)，查找复杂度为 O(n)；若每个表内部为顺序结构，则可用二分法将查找时间复杂度降至 O(logn)，但同时动态变化复杂度则变成 O(n)；顺序法是挨个查找，这种方法最容易实现，不过查找时间复杂度都是 O(n)，动态变化时可将保存值放入线性表尾部，则时间复杂度为 O(1)；二分法是基于顺序表的一种查找方式，时间复杂度为 O(logn)；通过哈希函数将值转化成存放该值的目标地址，O（1）
  2. 二叉树的平均查找长度为 O(log2n)——O(n). 二叉排序树的查找效率与二叉树的高度有关，高度越低，查找效率越高。二叉树的查找成功的平均查找长度 ASL 不超过二叉树的高度。二叉树的高度与二叉树的形态有关，n 个节点的完全二叉树高度最小，高度为 [log2n]+1,n 个节点的单只二叉树的高度最大，高度为 n，此时查找成功的 ASL 为最大 (n+1)/2，因此二叉树的高度范围为 [log2n]+1——n.
  3. 链式存储不能随机访问，必须是顺序存储

B_树的 B + 树

B_树

B + 树

哈希表

内部排序

  1. 内部排序：全部数据可同时放入内存进行的排序。
  2. 外部排序：文件中数据太多，无法全部调入内存进行的排序。

插入类：

  1. 直接插入排序。最坏情况是数据递减序，数据比较和移动量最大，达到 O(n2)，最好是数据是递增序，比较和移动最少为 O(n)。趟数是固定的 n-1，即使有序，也要依次从第二个元素开始。排序趟数不等于时间复杂度。
  2. 折半插入排序 。由于插入第 i 个元素到 r[1] 到 r[i-1] 之间时，前 i 个数据是有序的，所以可以用折半查找确定插入位置，然后插入。
  3. 希尔排序。缩小增量排序。5-3-1。在实际应用中，步长的选取可简化为开始为表长 n 的一半（n/2），以后每次减半，最后为 1。插入的改进，最后一趟已基本有序，比较次数和移动次数相比直接插入最后一趟更少

交换类：

  1. 冒泡排序。O(n2) 通常认为冒泡是比较差的，可以加些改进，比如在一趟中无数据的交换，则结束等措施。

    • 在数据已基本有序时，冒泡是一个较好的方法
    • 在数据量较少时（15 个左右）可以用冒泡

  2. 快速排序。

    • 时间复杂度。最好情况：每次支点总在中间，O(nlog2n)，平均 O(nlog2n)。最坏，数据已是递增或递减，O(n2)。pivotkey 的选择越靠近中央，即左右两个子序列长度越接近，排序速度越快。越无序越快。
    • 空间复杂度。需栈空间以实现递归，最坏情况：S(n)=O(n)；一般情况：S(n)=O(log2n)
    • 在序列已是有序的情况下，时间复杂度最高。原因：支点选择不当。改进：随机选取支点或最左、最右、中间三个元素中的值处于中间的作为支点，通常可以避免最坏情况。所以，快速排序在表已基本有序的情况下不合适。
    • 在序列长度已较短时，采用直接插入排序、起泡排序等排序方法。序列的个数通常取 10 左右。

选择类排序：

  1. 简单选择排序。O(n2)。总比较次数 n(n-1)/2。
  2. 堆排序。建堆 O(n)，筛选排序 O(nlogn)。找出若干个数中最大 / 最小的前 K 个数，用堆排序是最好。小根堆中最大的数一定是放在叶子节点上，堆本身是个完全二叉树，完全二叉树的叶子节点的位置大于 [n/2]。时间复杂度不会因为待排序序列的有序程度而改变，但是待排序序列的有序程度会影响比较次数。
  3. 归并排序。时间：与表长成正比，若一个表表长是 m，另一个是 n，则时间是 O(m+n)。单独一个数组归并，时间：O(nlogn)，空间：O(n)，比较次数介于 (nlogn)/2 和 (nlogn)-n+1，赋值操作的次数是 (2nlogn)。归并排序算法比较占用内存，但却是效率高且稳定的排序算法。在外排序中使用。归并的趟数是 logn。
  4. 基数排序。在一般情况下，每个结点有 d 位关键字，必须执行 t = d 次分配和收集操作。分配的代价：O(n)；收集的代价：O(rd) （rd 是基数）；总的代价为：O( d ×(n + rd))。适用于以数字和字符串为关键字的情况。
  5. 枚举排序，通常也被叫做秩排序，比较计数排序。对每一个要排序的元素，统计小于它的所有元素的个数，从而得到该元素在整个序列中的位置，时间复杂度为 O(n2)

比较法分类的下界：O(nlogn)

排序算法的一些特点：

  1. 堆排序、冒泡排序、快速排序在每趟排序过程中, 都会有一个元素被放置在其最终的位置上。
  2. 有字符序列 ｛Q,H,C,Y,P,A,M,S,R,D,F,X｝ , 新序列 {F,H,C,D,P,A,M,Q,R,S,Y,X}，是快速排序算法一趟扫描的结果。(拿 Q 作为分割点, 快速排序一轮。二路归并，第一趟排序，得到 n / 2 个长度为 2 的各自有序的子序列，第二趟排序，得到 n / 4 个长度为 4 的各自有序的子序列 H Q C Y A P M S D R F X。如果是快速排序的话，第一个元素 t 将会被放到一个最准确的位置，t 前的数均小于 t，后面的数均大于 t。希尔排序每个小分组内将会是有序的。堆排序，把它构成一颗二叉树的时候，该堆要么就是大根堆，要么就是小根堆，第一趟 Y 排在最后；冒泡，那么肯定会有数据下沉的动作，第一趟有 A 在第一位。)
  3. 在文件” 局部有序” 或文件长度较小的情况下, 最佳内部排序的方法是直接插入排序。（归并排序要求待排序列已经部分有序，而部分有序的含义是待排序列由若干有序的子序列组成，即每个子序列必须有序，并且其时间复杂度为 O(nlog2n)；直接插入排序在待排序列基本有序时，每趟的比较次数大为降低，即 n-1 趟比较的时间复杂度由 O(n^2) 降至 O(n)。在待排序的元素序列基本有序或者每个元素距其最终位置不远也可用插入排序，效率最高的排序方法是插入排序）
  4. 排序趟数与序列的原始状态有关的排序方法是优化冒泡和快速排序法。(插入排序和选择排序不管序列的原始状态是什么都要执行 n-1 趟，优化冒泡和快排不一定。仔细理解排序的次数和比较次数的区别)
  5. 不稳定的排序方法：快排，堆排，希尔，选择
  6. 要与关键字的初始排列次序无关, 那么就是最好、最坏、一般的情况下排序时间复杂度不变, 总共有堆排序, 归并排序, 选择排序, 基数排序
  7. 快速排序、Shell 排序、归并排序、直接插入排序的关键码比较次数与记录的初始排列有关。折半插入排序、选择排序无关。(直接插入排序在完全有序的情况下每个元素只需要与他左边的元素比较一次就可以确定他最终的位置；折半插入排序，比较次数是固定的，与初始排序无关；快速排序，初始排序不影响每次划分时的比较次数，都要比较 n 次，但是初始排序会影响划分次数，所以会影响总的比较次数，但快排平均比较次数最小；归并排序在归并的时候，如果右路最小值比左路最大值还大，那么只需要比较 n 次，如果右路每个元素分别比左路对应位置的元素大，那么需要比较 2*n-1 次，所以与初始排序有关)
  8. 精俭排序，即一对数字不进行两次和两次以上的比较，插入和归并是 “精俭排序”。插入排序，前面是有序的，后面的每一个元素与前面有序的元素比较，比较过的就是有序的了，不会再比较一次。归并每次合并后，内部都是有序的，内部的元素之间不用再比较。选择排序，每次在后面的元素中找到最小的，找最小元素的过程是在没有排好序的那部分进行，所有肯定会比较多次。堆排序也需比较多次。

外部排序

  1. 生成合并段（run）：读入文件的部分记录到内存－> 在内存中进行内部排序－> 将排好序的这些记录写入外存，形成合并段－> 再读入该文件的下面的记录，往复进行，直至文件中的记录全部形成合并段为止。
  2. 外部合并：将上一阶段生成的合并段调入内存，进行合并，直至最后形成一个有序的文件。
  3. 外部排序指的是大文件的排序，即待排序的记录存储在外存储器上，待排序的文件无法一次装入内存，需要在内存和外部存储器之间进行多次数据交换，以达到排序整个文件的目的。外部排序最常用的算法是多路归并排序，即将原文件分解成多个能够一次性装入内存的部分，分别把每一部分调入内存完成排序。然后，对已经排序的子文件进行多路归并排序
  4. 不管初始序列是否有序, 冒泡、选择排序时间复杂度是 O(n^2), 归并、堆排序时间复杂度是 O(nlogn）
  5. 外部排序的总时间 = 内部排序（产出初始归并段）所需时间 + 外存信息读取时间 + 内部归并所需的时间

  6. 外排中使用置换选择排序的目的, 是为了增加初始归并段的长度。减少外存读写次数需要减小归并趟数

  7. 根据内存容量设若干个输入缓冲区和一个输出缓冲区。若采用二路归并，用两个输入缓冲。

  8. 归并的方法类似于归并排序的归并算法。增加的是对缓冲的监视，对于输入，一旦缓冲空，要到相应文件读后续数据，对于输出缓冲，一旦缓冲满，要将缓冲内容写到文件中去。
  9. 外排序和内排序不只是考虑内外排序算法的性能，还要考虑 IO 数据交换效率的问题，内存存取速度远远高于外存。影响外排序的时间因素主要是内存与外设交换信息的总次数

有效的算法设计

  1. 贪心法。Dijkstra 的最短路径 (时间复杂度 O(n2))；Prim 求最小生成树邻接表存储时是 O(n+e), 图 O(n2)；关键路径及关键活动的求法。
  2. 回溯法
  3. 分支限界法
  4. 分治法。分割、求解、合并。二分查找、归并排序、快速排序。
  5. 动态规划。Floyd-Warshall 算法求解图中所有点对之间最短路径时间复杂度为 O(n3)

动态规划解题的方法是一种高效率的方法，其时间复杂度通常为 O(n2)，O(n3) 等，可以解决相当大的信息量。（数塔在 n<=100 层时，可以在很短的时间内得到问题解）

  • 适用的原则：原则为优化原则，即整体优化可以分解为若干个局部优化。
  • 动态规划比穷举法具有较少的计算次数
  • 递归算法需要很大的栈空间，而动态规划不需要栈空间

贪心和动态规划的差别：

  1. 所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。
  2. 在动态规划算法中，每步所作的选择往往依赖于相关子问题的解。因而只有在解出相关子问题后，才能作出选择。而在贪心算法中，仅在当前状态下作出最好选择，即局部最优选择。然后再去解作出这个选择后产生的相应的子问题。
  3. 贪心算法所作的贪心选择可以依赖于以往所作过的选择，但决不依赖于将来所作的选择，也不依赖于子问题的解。正是由于这种差别，动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行, 以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为一个规模更小的子问题。

P 问题

  1. P 问题，如果它可以通过运行多项式次 (即运行时间至多是输入量大小的多项式函数的一种算法获得解决），可以找到一个能在多项式的时间里解决它的算法。—- 确定性问题
  2. NP 问题，虽然可以用计算机求解，但是对于任意常数 k，它们不能在 O(nk) 时间内得到解答，可以在多项式的时间里验证一个解的问题。所有的 P 类问题都是 NP 问题。
  3. NP 完全问题，知道有效的非确定性算法，但是不知道是否存在有效的确定性算法，同时，不能证明这些问题中的任何一个不存在有效的确定性算法。这类问题称为 NP 完全问题。