数据结构与算法 Big O 备忘录与现实
不论今天的计算机技术变化，新技术的出现，所有都是来自数据结构与算法基础。我们需要温故而知新。
算法、架构、策略、机器学习之间的关系。在过往和技术人员交流时，很多人对算法和架构之间的关系感到不可理解，算法是软的，架构是硬的，难道算法和架构还有什么关系不成？其实不然，算法和架构的关系非常紧密。在互联网时代，我们需要用算法处理的数据规模越来越大，要求的处理时间越来越短，单一计算机的处理能力是不可能满足需求的。而架构技术的发展，带来了很多不同特点的分布式计算平台。算法为了能够应用到这些分布式计算平台上，往往需要进化，例如：并行计算要求算法可以拆分为可并行计算的几个独立单位，但很多算法不具备这种可拆分特性，使得不能简单通过分布式计算来提高效率。这时候，为了实现分布式化的计算效果，需要将算法进行等效改写，使得其具有独立拆分性。另一方面，算法的发展，也反过来会对计算架构提出新的要求。
对算法和策略的关系亦是，不过这两个概念并不像算法和架构那样好解释。策略是解决具体问题的手段，而算法是解决一类问题的方法。解决一个具体问题，可能需要将问题分解为一个或者多个算法，一起作用来解决，也可能不需要算法。例如，对于个性化新闻，我们可能有一个策略是：重大新闻需要及时展现给用户；而实现的具体算法可能只包括“重大新闻挖掘算法”等。
机器学习是一类算法的统称，在一定的数据集合上，利用机器学习的算法，自动得到规律，来进行预测，机器学习领域常见的问题包括分类问题、回归问题等。而预测，尤其是对用户的偏好进行预测是推荐领域的核心问题之一，机器学习算法在解决此类问题上会发生很大的作用。
- 没有最好的算法，只有合适的算法。推荐算法和产品需求、应用场景、数据密切相关，不要相信有什么包打天下的算法；
- 数据是基础：数据充足而且质量高，简单算法也可以有不错的效果；反之，则多好的算法也不可能有好的效果；
- 木桶效应：算法策略要和用户需求、功能展现密切配合；（注：木桶原理又称短板理论，其核心内容为“一只木桶盛水的多少，并不取决于桶壁上最高的那块木块，而恰恰取决于桶壁上最短的那块。”）
- 一般而言，推荐算法都需要考虑是否能处理大数据，是否能大规模并行化。
正文
一、数据结构基础
数组
定义
- 按顺序连续存储数据元素，通常索引从0开始
- 以集合论中的元组为基础
- 数组是最古老，最常用的数据结构
知识要点
- 索引最优；不利于查找、插入和删除（除非在数组最末进行）
- 最基础的是线性数组或一维数组
数组长度固定，意味着声明数组时应指明长度 - 动态数组与一维数组类似，但为额外添加的元素预留了空间
如果动态数组已满，则把每一元素复制到更大的数组中 - 类似网格或嵌套数组，二维数组有 x 和 y 索引
时间复杂度
- O(1)索引：一维数组：O(1)，动态数组：O(1)
- O(n)查找：一维数组：O(n)，动态数组：O(n)
- O(log n)最优查找：一维数组：O(log n)，动态数组：O(log n)
- O(n)插入：一维数组：n/a，动态数组：O(n)
链表
定义
- 结点存储数据，并指向下一结点
最基础的结点包含一个数据和一个指针（指向另一结点）- 链表靠结点中指向下一结点的指针连接成链
要点
- 为优化插入和删除而设计，但不利于索引和查找
- 双向链表包含指向前一结点的指针
- 循环链表是一种终端结点指针域指向头结点的简单链表
- 堆栈通常由链表实现，不过也可以利用数组实现
堆栈是“后进先出”（LIFO）的数据结构- 由链表实现时，只有头结点处可以进行插入或删除操作
- 同样地，队列也可以通过链表或数组实现
队列是“先进先出”（FIFO）的数据结构- 由双向链表实现时，只能在头部删除，在末端插入
时间复杂度
- O(n)索引：链表：O(n)
- O(n)查找：链表：O(n)
- Linked Lists: O(n)最优查找：链表：O(n)
- O(1)插入：链表：O(1)
哈希表或哈希图
定义
- 通过键值对进行储存
- 哈希函数接受一个关键字，并返回该关键字唯一对应的输出值
这一过程称为散列（hashing），是输入与输出一一对应的概念- 哈希函数为该数据返回在内存中唯一的存储地址
要点
- 为查找、插入和删除而设计
- 哈希冲突是指哈希函数对两个不同的数据项产生了相同的输出值
所有的哈希函数都存在这个问题- 用一个非常大的哈希表，可以有效缓解这一问题
- 哈希表对于关联数组和数据库检索十分重要
时间复杂度
- O(1)索引：哈希表：O(1)
- O(1)查找：哈希表：O(1)
- O(1)插入：哈希表：O(1)
二叉树
定义
- 一种树形的数据结构，每一结点最多有两个子树
- 子结点又分为左子结点和右子结点
要点
- 为优化查找和排序而设计
- 退化树是一种不平衡的树，如果完全只有一边，其本质就是一个链表
- 相比于其他数据结构，二叉树较为容易实现
- 可用于实现二叉查找树
- 二叉树利用可比较的键值来确定子结点的方向
- 左子树有比双亲结点更小的键值
- 右子树有比双亲结点更大的键值
- 重复的结点可省略
- 由于上述原因，二叉查找树通常被用作一种数据结构，而不是二叉树
时间复杂度
- 索引：二叉查找树：O(log n)
- 查找：二叉查找树：O(log n)
- 插入：二叉查找树：O(log n)
二、搜索基础
广度优先搜索
定义
- 一种在树（或图）中进行搜索的算法，从根结点开始，优先按照树的层次进行搜索
- 搜索同一层中的各结点，通常从左往右进行
- 进行搜索时，同时追踪当前层中结点的子结点
- 当前一层搜索完毕后，转入遍历下一层中最左边的结点
- 最下层最右端是最末结点（即该结点深度最大，且在当前层次的最右端）
要点
- 当树的宽度大于深度时，该搜索算法较优
- 进行树的遍历时，使用队列存储树的信息
- 原因是：使用队列比深度优先搜索更为内存密集
- 由于需要存储指针，队列需要占用更多内存
时间复杂度
- O(|E| + |V|)查找：广度优先搜索：O(|E| + |V|)
- E 是边的数目
- V 是顶点的数目
深度优先搜索
定义
- 一种在树（或图）中进行搜索的算法，从根结点开始，优先按照树的深度进行搜索
- 从左边开始一直往下遍历树的结点，直到不能继续这一操作
- 一旦到达某一分支的最末端，将返回上一结点并遍历该分支的右子结点，如果可以将从左往右遍历子结点
- 当前这一分支搜索完毕后，转入根节点的右子结点，然后不断遍历左子节点，直到到达最底端
- 最右的结点是最末结点（即所有祖先中最右的结点）
要点
- 当树的深度大于宽度时，该搜索算法较优
- 利用堆栈将结点压栈
- 因为堆栈是“后进先出”的数据结构，所以无需跟踪结点的指针。与广度优先搜索相比，它对内存的要求不高。
- 一旦不能向左继续遍历，则对栈进行操作
时间复杂度
- O(|E| + |V|)查找：深度优先搜索：O(|E| + |V|)
- E 是边的数目
- V 是结点的数目
广度优先搜索 VS. 深度优先搜索
- 这一问题最简单的回答就是，选取何种算法取决于树的大小和形态
- 就宽度而言，较浅的树适用广度优先搜索
- 就深度而言，较窄的树适用深度优先搜索
细微的区别
- 由于广度优先搜索（BFS）使用队列来存储结点的信息和它的子结点，所以需要用到的内存可能超过当前计算机可提供的内存（不过其实你不必担心这一点）
- 如果要在某一深度很大的树中使用深度优先搜索（DFS），其实在搜索中大可不必走完全部深度。可在 xkcd 上查看更多相关信息。
- 广度优先搜索趋于一种循环算法。
- 深度优先搜索趋于一种递归算法
三、高效排序基础
归并排序
定义
- 一种基于比较的排序算法
- 将整个数据集划分成至多有两个数的分组
- 依次比较每个数字，将最小的数移动到每对数的左边
- 一旦所有的数对都完成排序，则开始比较最左两个数对中的最左元素，形成一个含有四个数的有序集合，其中最小数在最左边，最大数在最右边
- 重复上述过程，直到归并成只有一个数据集
要点
- 这是最基础的排序算法之一
- 必须理解：首先将所有数据划分成尽可能小的集合，再作比较
时间复杂度
- O(n)最好的情况：归并排序：O(n)
- 平均情况：归并排序：O(n log n)
- 最坏的情况：归并排序：O(n log n)
快速排序
定义
- 一种基于比较的排序算法
- 通过选取平均数将整个数据集划分成两部分，并把所有小于平均数的元素移动到平均数左边
- 在左半部分重复上述操作，直到左边部分的排序完成后，对右边部分执行相同的操作
- 计算机体系结构支持快速排序过程
要点
- 尽管快速排序与许多其他排序算法有相同的时间复杂度（有时会更差），但通常比其他排序算法执行得更快，例如归并排序。
- 必须理解：不断通过平均数将数据集对半划分，直到所有的数据都完成排序
时间复杂度
- O(n)最好的情况：归并排序：O(n)
- O(n log n)平均情况：归并排序：O(n log n)
- 最坏的情况：归并排序：O(n2)
冒泡排序
定义
- 一种基于比较的排序算法
- 从左往右重复对数字进行两两比较，把较小的数移到左边
- 重复上述步骤，直到不再把元素左移
要点
- 尽管这一算法很容易实现，却是这三种排序方法中效率最低的
- 必须理解：每次向右移动一位，比较两个元素，并把较小的数左移
时间复杂度
- O(n)最好的情况：归并排序：O(n)
- O(n2)平均情况：归并排序： O(n2)
- O(n2)最坏的情况：归并排序： O(n2)
归并排序 VS. 快速排序
- 在实践中，快速排序执行速率更快
- 归并排序首先将集合划分成最小的分组，在对分组进行排序的同时，递增地对分组进行合并
- 快速排序不断地通过平均数划分集合，直到集合递归地有序
四、算法类型基础
递归算法
定义
- 在定义过程中调用其本身的算法
- 递归事件：用于触发递归的条件语句
- 基本事件：用于结束递归的条件语句
要点
- 堆栈级过深和栈溢出
- 如果在递归算法中见到上述两种情况中的任一个，那就糟糕了
- 那就意味着因为算法错误，或者问题规模太过庞大导致问题解决前 RAM 已耗尽，从而基本事件从未被触发
- 必须理解：不论基本事件是否被触发，它在递归中都不可或缺
- 通常用于深度优先搜索
迭代算法
定义
- 一种被重复调用有限次数的算法，每次调用都是一次迭代
- 通常用于数据集中递增移动
要点
- 通常迭代的形式为循环、for、while和until语句
- 把迭代看作是在集合中依次遍历每个元素
- 通常用于数组的遍历
递归 VS. 迭代
- 由于递归和迭代可以相互实现，两者之间的区别很难清晰地界定。但必须知道：
- 通常递归的表意性更强，更易于实现
- 迭代占用的内存更少
- (i.e. Haskell)函数式语言趋向于使用递归（如 Haskell 语言）
- 命令式语言趋向于使用迭代（如 Ruby 语言）
- 点击 Stack Overflow post 了解更多详情
遍历数组的伪代码（这就是为什么使用迭代的原因）
Recursion | Iteration
----------------------------------|----------------------------------
recursive method (array, n) | iterative method (array)
if array[n] is not nil | for n from 0 to size of array
print array[n] | print(array[n])
recursive method(array, n+1) |
else |
exit loop
贪婪算法
定义
- 一种算法，在执行的同时只选择满足某一条件的信息
- 通常包含5个部分，摘自维基百科：
- 候选集，从该集合中可得出解决方案
- 选择函数，该函数选取要加入解决方案中的最优候选项
- 可行性函数，该函数用于决策某一候选项是否有助于解决方案
- 目标函数，该函数为解决方案或部分解赋值
- 解决方案函数，该函数将指明完整的解决方案
要点
- 用于找到预定问题的最优解
- 通常用于只有少部分元素能满足预期结果的数据集合
- 通常贪婪算法可帮助一个算法降低时间 复杂度
伪代码：用贪婪算法找到数组中任意两个数字间的最大差值
greedy algorithm (array)
var largest difference = 0
var new difference = find next difference (array[n], array[n+1])
largest difference = new difference if new difference is > largest difference
repeat above two steps until all differences have been found
return largest difference
这一算法无需比较所有数字两两之间的差值，省略了一次完整迭代。
以下是Big O 核对表
Legend
| Excellent | Good | Fair | Bad | Horrible |
Data Structure Operations
| Data Structure | Time Complexity |
|
|
|
|
|
|
| Space Complexity |
|
| Average |
|
|
| Worst |
|
|
| Worst |
|
| Access | Search | Insertion | Deletion | Access | Search | Insertion | Deletion |
|
| Array | O(1) | O(n) | O(n) | O(n) | O(1) | O(n) | O(n) | O(n) | O(n) |
| Stack | O(n) | O(n) | O(1) | O(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
| Singly-Linked List | O(n) | O(n) | O(1) | O(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
| Doubly-Linked List | O(n) | O(n) | O(1) | O(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
| Skip List | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(n) | O(n) | O(n) | O(n) | O(n log(n)) |
| Hash Table | - | O(1) | O(1) | O(1) | - | O(n) | O(n) | O(n) | O(n) |
| Binary Search Tree | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(n) | O(n) | O(n) | O(n) | O(n) |
| Cartesian Tree | - | O(log(n)) | O(log(n)) | O(log(n)) | - | O(n) | O(n) | O(n) | O(n) |
| B-Tree | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(n) |
| Red-Black Tree | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(n) |
| Splay Tree | - | O(log(n)) | O(log(n)) | O(log(n)) | - | O(log(n)) | O(log(n)) | O(log(n)) | O(n) |
| AVL Tree | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(n) |
Array Sorting Algorithms
| Algorithm | Time Complexity |
|
| Space Complexity |
|
| Best | Average | Worst | Worst |
| Quicksort | O(n log(n)) | O(n log(n)) | O(n^2) | O(log(n)) |
| Mergesort | O(n log(n)) | O(n log(n)) | O(n log(n)) | O(n) |
| Timsort | O(n) | O(n log(n)) | O(n log(n)) | O(n) |
| Heapsort | O(n log(n)) | O(n log(n)) | O(n log(n)) | O(1) |
| Bubble Sort | O(n) | O(n^2) | O(n^2) | O(1) |
| Insertion Sort | O(n) | O(n^2) | O(n^2) | O(1) |
| Selection Sort | O(n^2) | O(n^2) | O(n^2) | O(1) |
| Shell Sort | O(n) | O((nlog(n))^2) | O((nlog(n))^2) | O(1) |
| Bucket Sort | O(n+k) | O(n+k) | O(n^2) | O(n) |
| Radix Sort | O(nk) | O(nk) | O(nk) | O(n+k) |
Graph Operations
| Node / Edge Management | Storage | Add Vertex | Add Edge | Remove Vertex | Remove Edge | Query |
| Adjacency list | O(|V|+|E|) | O(1) | O(1) | O(|V| + |E|) | O(|E|) | O(|V|) |
| Incidence list | O(|V|+|E|) | O(1) | O(1) | O(|E|) | O(|E|) | O(|E|) |
| Adjacency matrix | O(|V|^2) | O(|V|^2) | O(1) | O(|V|^2) | O(1) | O(1) |
| Incidence matrix | O(|V| ⋅ |E|) | O(|V| ⋅ |E|) | O(|V| ⋅ |E|) | O(|V| ⋅ |E|) | O(|V| ⋅ |E|) | O(|E|) |
Heap Operations
| Type | Time Complexity |
|
|
|
|
|
|
|
| Heapify | Find Max | Extract Max | Increase Key | Insert | Delete | Merge |
| Linked List (sorted) | - | O(1) | O(1) | O(n) | O(n) | O(1) | O(m+n) |
| Linked List (unsorted) | - | O(n) | O(n) | O(1) | O(1) | O(1) | O(1) |
| Binary Heap | O(n) | O(1) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(m+n) |
| Binomial Heap | - | O(1) | O(log(n)) | O(log(n)) | O(1) | O(log(n)) | O(log(n)) |
| Fibonacci Heap | - | O(1) | O(log(n)) | O(1) | O(1) | O(log(n)) | O(1) |
Big-O Complexity Chart
计算机科学中最重要的32个算法
- 查找：判断某特定元素属于哪个组。
- 合并：联合或合并两个组为一个组。
现实中算法
Linux内核中的基本数据结构和算法
B+ 树，代码中的注释将会告诉你一些教科书中不能学到的内容：
这是一个简单的B+树实现，我写它的目的是作为练习，并以此了解B+树的工作原理。结果该实现发挥了它的实用价值。
...
一个不经常在教科书中提及的技巧：最小值应该放在右侧，而不是左侧。一个节点内所有被使用的槽位应该在左侧，没有使用的节点应该为NUL，大部分的操作只遍历一次所有的槽位，在第一个NUL处终止。
带权重的有序列表用于互斥锁、驱动等；
radix树的一个常见的用法是保存页面结构体的指针；
包含指针的只允许简单插入的静态大小优先级堆，基于CLR（算法导论）第七章
哈希函数，引用Knuth和他的一篇论文：
Knuth建议选择与机器字长所能表达的最大整数约成黄金比例的素数来做乘法散列，Chuck Lever 证实了这个技术的有效性；
http://www.citi.umich.edu/techreports/reports/citi-tr-00-1.pdf
这些选择的素数是位稀疏的，也就是说对他们的操作可以使用位移和加法来替换机器中很慢的乘法操作；
有些代码，比如这个驱动，他们是自己实现的哈希函数
在命名空间树中执行一个修改过的深度优先算法，开始（和终止于）start_handle所确定的节点。当与参数匹配的节点被发现以后，回调函数将会被调用。如果回调函数返回一个非空的值，搜索将会立即终止，这个值将会回传给调用函数；
Knuth-Morris-Pratt 字符串匹配；
Knuth、Morris和 Pratt [1]实现了一个线性时间复杂度字符串匹配算法。该算法完全规避了对转换函数DELTA的显式计算。其匹配时间为O(n)（其中n是文本长度），只使用一个辅助函数PI[1...m]（其中m是模式的长度），模式的预处理时间是O(m)。PI这个数组允许DELTA函数在需要时能迅速运行。大体上，对任意状态q=0,1,...,m和任意SIGMA中的字符"a"，PI["q"]保存了独立于"a"的信息，并用于计算DELTA("q", "a")。由于PI这个数组只包含m个条目，而DELTA包含O(m|SIGMA|)个条目，我们通过计算PI进而在预处理时间保存|SIGMA|的系数，而非计算DELTA。
[1] Cormen, Leiserson, Rivest, Stein Introdcution to Algorithms, 2nd Edition, MIT Press
[2] See finite automation theory
Boyer-Moore模式匹配，如下是引用和对其他算法的使用建议；
Boyer-Moore字符串匹配算法:
[1] A Fast String Searching Algorithm, R.S. Boyer and Moore. Communications of the Association for Computing Machinery, 20(10), 1977, pp. 762-772. http://www.cs.utexas.edu/users/moore/publications/fstrpos.pdf
[2] Handbook of Exact String Matching Algorithms, Thierry Lecroq, 2004 http://www-igm.univ-mlv.fr/~lecroq/string/string.pdf
注意：由于Boyer-Moore（BM）自右向左做匹配，有一种可能性是一个匹配分布在不同的块中，这种情况下是不能找到任何匹配的。
如果你想确保这样的事情不会发生，使用Knuth-Pratt-Morris（KMP）算法来替代。也就是说，根据你的设置选择合适的字符串查找算法。
如果你使用文本搜索架构来过滤、网络入侵检测（NIDS）或者任何安全为目的，那么选择KMP。如果你关乎性能，比如你在分类数据包，并应用服务质量（QoS）策略，并且你不介意可能需要在分布在多个片段中匹配，然后就选择BM。
Chromium 浏览器中的数据结构和算法
此树会被分配策略参数化，这个策略负责在C的自由存储空间和区域中分配列表，参见zone.h
同时，代码中还包含了一些第三方的算法和数据结构，例如：
编程语言类库
分配和调度算法
*nix系统中的核心组件
加密算法
编译器
压缩和图片处理
为GIF图片格式而出现的Lempel-Zivsraf算法在图片处理程序中经常被应用，从一个简单的*nix组件转化为一个复杂的程序；
运行长度编码被用于生成PCX文件（用于Paintbrush这个程序中），压缩BMP文件和TIFF文件；
小波压缩（Wavelet压缩）是JPEG 2000的基础，所以所有生成JPEG 2000文件的数码相机都是实现了这个算法；
Reed-Solomon纠错用于Linux内核、CD驱动、条形码读取，并且结合卷积从航行团队进行图片传输；
冲突驱动条款学习算法（Conflict Driven Clause Learning）
自2000年以来，在工业标准中的SAT（布尔满足性问题）求解器的运行时间每年都在成倍减少。这一发展的一个非常重要的原因是冲突驱动条款学习算法（Conflict Driven Clause Learning）的使用，它结合了Davis Logemann和Loveland的约束编程和人工智能研究技术的原始论文中关于布尔约束传播的算法。具体来说，工业建模中SAT被认为是一个简单的问题（见讨论）。对我来说，这是近代最伟大的成功故事之一，因为它结合了先进的算法、巧妙的设计思路、实验反馈，并以一致的共同努力来解决这个问题。Malik和Zhang的CACM论文是一个很好的阅读材料。许多大学都在教授这个算法，但通常是在逻辑或形式化方法的课程中。
希望对您企业应用开发与企业信息化有帮助。 其它您可能感兴趣的文章：
《视觉直观感受 7 种常用的排序算法》
《匈牙利 Sapientia 大学的 6 种排序算法舞蹈视频》
《视频：6 分钟演示 15 种排序算法》
《SORTING：可视化展示排序算法的原理，支持单步查看》
《VisuAlgo：通过动画学习算法和数据结构》
软件开发的专业化
IT基础架构规划方案一(网络系统规划)
IT基础架构规划方案二(计算机系统与机房规划规划)
IT基础架构规划方案三(IT基础软件和系统规划)
企业应用之性能实时度量系统演变
云计算参考架构几例
智能移动导游解决方案简介
人力资源管理系统的演化
如有想了解更多软件研发 , 系统 IT集成 , 企业信息化 等资讯，请关注我的微信订阅号：
作者：Petter Liu
出处：http://www.cnblogs.com/wintersun/
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。
该文章也同时发布在我的独立博客中-Petter Liu Blog。
转载于:https://www.cnblogs.com/wintersun/p/4840585.html
总结
以上是生活随笔为你收集整理的数据结构与算法 Big O 备忘录与现实的全部内容，希望文章能够帮你解决所遇到的问题。
- 上一篇： QQ聊天文字背影图片拉伸方法
- 下一篇： java 添加一个线程、创建响应的用户界