一般情况，我们可以把整个数据结构存储到计算机的主存中；可如果数据更多装不下主存，那么意味着必须把数据结构放到磁盘上。 此时“大O模型”不再适用，因为大O分析假设所有操作耗时都是相同的，所以涉及到磁盘I/O就不再适用了。与内存相比，磁盘必须花成倍的时间来存取一个数据元素，这是因为磁盘的机械部件读写数据的速度远远赶不上纯电子媒体的内存。 【CPU】 <—> 【内存】 …

阅读更多

数据结构可以看作是算法实现的容器，通过一系列特殊结构的数据集合，能够将算法更为高效而可靠的执行起来。 算法（Algorithm）是为了解决一个特定的问题而精心设计的一套数学模型以及在这套数学模型上的一系列操作步骤，这些操作步骤是将描述的输入数据逐步处理、转换，并最后得到一个确定的结果。 一般来说，算法设计没有什么固定的方法可循。但是通过大量的实践，也总结出算法某些共性的规律，包括枚 …

阅读更多

Trie 树，也叫“字典树”、“前缀树”。它是一种有序树形结构。是一种专门处理字符串匹配的数据结构，用来解决在一组字符串集合中快速查找某个字符串的问题。 AC 自动机以Trie 树的结构为基础，结合KMP的思想建立的，是一种用于解决多模式匹配问题的经典算法。

1. Trie 树 Trie 树的本质，就是利用字符串之间的公共前缀，将重复的前缀合并在一起。 举例说明一下。我们有6个字符 …

阅读更多

介绍字符串匹配算法之前，先定义几个概念： 主串Text: 长度记作 n； 模式串Pattern: 长度记作 m，并且 m<=n。 有效位移s（Valid Shift）：即模式串在主串中出现，并且位置移动 s 次。 1. BF 算法 BF（Brute Force）算法，中文叫作暴力匹配算法，也叫朴素匹配算法。 从主串的首或尾开始逐个匹配字母（比较顺序没有限制）。 BF 算法的思想可以用一句话来 …

阅读更多

二分查找（Binary Search）又称折半查找、二分搜索、折半搜索等，查找思想有点类似分治思想，对应的时间复杂度为O(logn)。 二分查找算法仅适用于有序且使用顺序存储结构的序列（比如有序数组）。 核心思想是：不断地缩小搜索区域，降低查找目标元素的难度。（每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。） 以在升序序列中查找目标元素 …

阅读更多

排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。 用一张图概括： 名词解释： n：数据规模 k：“桶"的个数 In-place：占用常数内存， …

阅读更多

图（Graph）。和树比起来，这是一种更加复杂的非线性表结构，由顶点和连接每对顶点的边所构成的抽象网络就是图。 图的定义：图是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G(V,E)，其中，G表示一个图，V是顶点的集合，E是边的集合。 图中的元素叫做顶点（vertex）。顶点与其他顶点建立的连接关系叫做边（edge）。跟顶点相连接的边的条数叫做顶点的度（degree）。 如果图中任意两 …

阅读更多

堆的两点要求： 堆是一个完全二叉树； 堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值。 对于每个节点的值都大于等于子树中每个节点值的堆，我们叫做大顶堆。 对于每个节点的值都小于等于子树中每个节点值的堆，我们叫做小顶堆。 完全二叉树：除最后一层外，其他层的节点都满；并且最后一层的节点从左到右是连续排列，中间没有断开，空位都在右边。 在构建完全二叉树的时候，新加入的节点在最后一层从 …

阅读更多

平衡二叉查找树其实有很多，比如，红黑树（Red-Black Tree，简称 R-B Tree）、伸展树（Splay Tree）、树堆（Treap）等，但是我们提到平衡二叉查找树，听到的基本都是红黑树，它是一种不严格的平衡二叉查找树。 红黑树是一种含有红黑节点并能自平衡的二叉查找树。它必须满足下面性质： 每个节点要么是红色，要么是黑色； 根节点是黑色的； 每个叶子节点都是黑色的空节点（NIL），也就 …

阅读更多

AVL树（得名于发明者G. M. Adelson-Velsky 和 E. M. Landis）本质上是一棵带有平衡条件的二叉搜索树。 AVL树具有以下2个性质： 左子树和右子树的深度之差的绝对值不超过1； 左子树和右子树全都是 AVL树。 其中为了度量左右子树的深度之差，我们引入平衡因子(BF)的概念。 平衡因子： 某个节点的左子树的高度减去右子树的高度得到的差值。 对于一棵 AVL树，里面的所有 …

阅读更多