themeConfig: {

nav: [],

sidebarDepth: 2, // 侧边栏显示深度，默认1，最大2（显示到h3标题）

repo: 'dunwu/algorithm-tutorial', // 导航栏右侧生成Github链接

searchMaxSuggestions: 10, // 搜索结果显示最大数

lastUpdated: '上次更新', // 更新的时间，及前缀文字 string | boolean (取值为git提交时间)

【示例】递归函数的时间复杂度是多少？思考一下斐波那契数列 `f(n) = f(n-1) + f(n-2)` 的时间复杂度是多少？

在数据量比较小的时候，复杂度量级差异并不明显；但是，随着数据规模大小的变化，差异会逐渐突出。

`O(1)` 复杂度示例：

数组元素的访问是以行或列索引的单一下标表示。

在上面的例子中，数组 a 中有 5 个元素。`也就是说`，a 的长度是 6 。我们可以使用 a[0] 来表示数组中的第一个元素。因此，a[0] = A 。类似地，a[1] = B，a[2] = C，依此类推。

下图是由 M 个行向量，N 个列向量组成的二维数组.

单链表中的每个结点不仅包含数据值，还包含一个指针，指向其后继节点。通过这种方式，单链表将所有结点按顺序组织起来。

与数组不同，我们无法在常量时间内访问单链表中的随机元素。 如果我们想要获得第 i 个元素，我们必须从头结点逐个遍历。 我们按 `索引` 来 `访问元素` 平均要花费 `O(N)` 时间，其中 N 是链表的长度。

（1）使用给定值初始化新结点 `cur`；

（2）将 `cur` 的 `next` 字段链接到 `prev` 的下一个结点 `next` ；

（3）将 `prev` 中的 `next` 字段链接到 `cur` 。

与数组不同，我们不需要将所有元素移动到插入元素之后。因此，您可以在 `O(1)` 时间复杂度中将新结点插入到链表中，这非常高效。

（1）找到 `cur` 的上一个结点 `prev` 及其下一个结点 `next` ；

（2）接下来链接 `prev` 到 `cur` 的下一个节点 `next` 。

在我们的第一步中，我们需要找出 `prev` 和 `next`。使用 `cur` 的参考字段很容易找出 `next`，但是，我们必须从头结点遍历链表，以找出 `prev`，它的平均时间是 `O(N)`，其中 `N` 是链表的长度。因此，删除结点的时间复杂度将是 `O(N)`。

单链表的访问是单向的，而双链表的访问是双向的。显然，双链表比单链表操作更灵活，但是空间开销也更大。

双链表以类似的方式工作，但`还有一个引用字段`，称为`“prev”`字段。有了这个额外的字段，您就能够知道当前结点的前一个结点。

（1）使用给定值初始化新结点 `cur`；

（2）链接 `cur` 与 `prev` 和 `next`，其中 `next` 是 `prev` 原始的下一个节点；

（3）用 `cur` 重新链接 `prev` 和 `next`。

与单链表类似，添加操作的时间和空间复杂度都是 `O(1)`。

- 单链表的最后一个结点的后继指针 `next` 指向空地址。

- 循环链表的最后一个结点的后继指针 `next` 指向第一个节点（如果有头节点，就指向头节点）。

**栈是一个 LIFO(后进先出) 数据结构**。**栈是一种“操作受限”的线性表**，只允许在一端插入和删除数据。通常，插入操作在栈中被称作入栈 push 。与队列类似，总是在堆栈的末尾添加一个新元素。但是，删除操作，退栈 pop ，将始终删除队列中相对于它的最后一个元素。

**当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性，我们就应该首选“栈”这种数据结构**。

（1）**函数调用栈**

（2）**表达式求值**

（3）**表达式匹配**

队列的最基本操作：**入队 `enqueue()`**，放一个数据到队列尾部；**出队 `dequeue()`**，从队列头部取一个元素。

队列可以用数组来实现，也可以用链表来实现。用数组实现的队列叫作**顺序队列**，用链表实现的队列叫作**链式队列**。

在用数组实现的非循环队列中，队满的判断条件是 `(tail+1) % n == head`，队空的判断条件是 `head == tail`。

- 在队列为空的时候，从队头取数据会被阻塞。因为此时还没有数据可取，直到队列中有了数据才能返回；

- 如果队列已经满了，那么插入数据的操作就会被阻塞，直到队列中有空闲位置后再插入数据，然后再返回。

（2）**并发队列**

假设有一个大小为 N 的无序序列。冒泡排序就是要每趟排序过程中通过两两比较，找到第 i 个小（大）的元素，将其往上排。

以上图为例，演示一下冒泡排序的实际流程：

详细的图解往往比大堆的文字更有说明力，所以直接上图：

上图中，演示了快速排序的处理过程：

在讲解直接插入排序之前，先让我们脑补一下我们打牌的过程。

- 先拿一张 5 在手里，

- 再摸到一张 4，比 5 小，插到 5 前面，

我们来通过演示图，更深入的理解一下这个过程。

在上面这幅图中：

**核心代码**

其中 i=1,2,…,n/2 向下取整;

如上图所示，序列 R{3, 8,15, 31, 25} 是一个典型的小根堆。

设有一个无序序列 { 1, 3,4, 5, 2, 6, 9, 7, 8, 0 }。

构造了初始堆后，我们来看一下完整的堆排序处理：

还是针对前面提到的无序序列 { 1,3, 4, 5, 2, 6, 9, 7, 8, 0 } 来加以说明。

相信，通过以上两幅图，应该能很直观的演示堆排序的操作处理。

掌握了合并的方法，接下来，让我们来了解**如何分解**。

在某趟归并中，设各子表的长度为 **gap**，则归并前 R[0...n-1] 中共有 **n/gap** 个有序的子表：`R[0...gap-1]`, `R[gap...2*gap-1]`, ... , `R[(n/gap)*gap ... n-1]`。

我们先根据序列的个位数的数字来进行分类，将其分到指定的桶中。例如：R[0] = 50，个位数上是 0，将这个数存入编号为 0 的桶中。

分类后，我们在从各个桶中，将这些数按照从编号 0 到编号 9 的顺序依次将所有数取出来。