数据结构与算法 Big O 备忘录与现实

不论今天的计算机技术变化，新技术的出现，所有都是来自数据结构与算法基础。我们需要温故而知新。

       算法、架构、策略、机器学习之间的关系。在过往和技术人员交流时，很多人对算法和架构之间的关系感到不可理解，算法是软的，架构是硬的，难道算法和架构还有什么关系不成？其实不然，算法和架构的关系非常紧密。在互联网时代，我们需要用算法处理的数据规模越来越大，要求的处理时间越来越短，单一计算机的处理能力是不可能满足需求的。而架构技术的发展，带来了很多不同特点的分布式计算平台。算法为了能够应用到这些分布式计算平台上，往往需要进化，例如：并行计算要求算法可以拆分为可并行计算的几个独立单位，但很多算法不具备这种可拆分特性，使得不能简单通过分布式计算来提高效率。这时候，为了实现分布式化的计算效果，需要将算法进行等效改写，使得其具有独立拆分性。另一方面，算法的发展，也反过来会对计算架构提出新的要求。

       对算法和策略的关系亦是，不过这两个概念并不像算法和架构那样好解释。策略是解决具体问题的手段，而算法是解决一类问题的方法。解决一个具体问题，可能需要将问题分解为一个或者多个算法，一起作用来解决，也可能不需要算法。例如，对于个性化新闻，我们可能有一个策略是：重大新闻需要及时展现给用户；而实现的具体算法可能只包括“重大新闻挖掘算法”等。

      机器学习是一类算法的统称，在一定的数据集合上，利用机器学习的算法，自动得到规律，来进行预测，机器学习领域常见的问题包括分类问题、回归问题等。而预测，尤其是对用户的偏好进行预测是推荐领域的核心问题之一，机器学习算法在解决此类问题上会发生很大的作用。

正文

四、算法类型基础

递归算法

定义

• 在定义过程中调用其本身的算法
  • 递归事件：用于触发递归的条件语句
  • 基本事件：用于结束递归的条件语句

要点

• 堆栈级过深和栈溢出
  • 如果在递归算法中见到上述两种情况中的任一个，那就糟糕了
  • 那就意味着因为算法错误，或者问题规模太过庞大导致问题解决前 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

Data Structure Operations

Array Sorting Algorithms

Graph Operations

Heap Operations

Big-O Complexity Chart

计算机科学中最重要的32个算法

1. A* 搜索算法——图形搜索算法，从给定起点到给定终点计算出路径。其中使用了一种启发式的估算，为每个节点估算通过该节点的最佳路径，并以之为各个地点排定次序。算法以得到的次序访问这些节点。因此，A*搜索算法是最佳优先搜索的范例。
2. 集束搜索（又名定向搜索，Beam Search）——最佳优先搜索算法的优化。使用启发式函数评估它检查的每个节点的能力。不过，集束搜索只能在每个深度中发现最前面的m个最符合条件的节点，m是固定数字——集束的宽度。
3. 二分查找（Binary Search）——在线性数组中找特定值的算法，每个步骤去掉一半不符合要求的数据。
4. 分支界定算法（Branch and Bound）——在多种最优化问题中寻找特定最优化解决方案的算法，特别是针对离散、组合的最优化。
5. Buchberger算法——一种数学算法，可将其视为针对单变量最大公约数求解的欧几里得算法和线性系统中高斯消元法的泛化。
6. 数据压缩——采取特定编码方案，使用更少的字节数（或是其他信息承载单元）对信息编码的过程，又叫来源编码。
7. Diffie-Hellman密钥交换算法——一种加密协议，允许双方在事先不了解对方的情况下，在不安全的通信信道中，共同建立共享密钥。该密钥以后可与一个对称密码一起，加密后续通讯。
8. Dijkstra算法——针对没有负值权重边的有向图，计算其中的单一起点最短算法。
9. 离散微分算法（Discrete differentiation）
10. 动态规划算法（Dynamic Programming）——展示互相覆盖的子问题和最优子架构算法
11. 欧几里得算法（Euclidean algorithm）——计算两个整数的最大公约数。最古老的算法之一，出现在公元前300前欧几里得的《几何原本》。
12. 期望-最大算法（Expectation-maximization algorithm，又名EM-Training）——在统计计算中，期望-最大算法在概率模型中寻找可能性最大的参数估算值，其中模型依赖于未发现的潜在变量。EM在两个步骤中交替计算，第一步是计算期望，利用对隐藏变量的现有估计值，计算其最大可能估计值；第二步是最大化，最大化在第一步上求得的最大可能值来计算参数的值。
13. 快速傅里叶变换（Fast Fourier transform，FFT）——计算离散的傅里叶变换（DFT）及其反转。该算法应用范围很广，从数字信号处理到解决偏微分方程，到快速计算大整数乘积。
14. 梯度下降（Gradient descent）——一种数学上的最优化算法。
15. 哈希算法（Hashing）
16. 堆排序（Heaps）
17. Karatsuba乘法——需要完成上千位整数的乘法的系统中使用，比如计算机代数系统和大数程序库，如果使用长乘法，速度太慢。该算法发现于1962年。
18. LLL算法（Lenstra-Lenstra-Lovasz lattice reduction）——以格规约（lattice）基数为输入，输出短正交向量基数。LLL算法在以下公共密钥加密方法中有大量使用：背包加密系统（knapsack）、有特定设置的RSA加密等等。
19. 最大流量算法（Maximum flow）——该算法试图从一个流量网络中找到最大的流。它优势被定义为找到这样一个流的值。最大流问题可以看作更复杂的网络流问题的特定情况。最大流与网络中的界面有关，这就是最大流-最小截定理（Max-flow min-cut theorem）。Ford-Fulkerson 能找到一个流网络中的最大流。
20. 合并排序（Merge Sort）
21. 牛顿法（Newton‘s method）——求非线性方程（组）零点的一种重要的迭代法。
22. Q-learning学习算法——这是一种通过学习动作值函数（action-value function）完成的强化学习算法，函数采取在给定状态的给定动作，并计算出期望的效用价值，在此后遵循固定的策略。Q-leanring的优势是，在不需要环境模型的情况下，可以对比可采纳行动的期望效用。
23. 两次筛法（Quadratic Sieve）——现代整数因子分解算法，在实践中，是目前已知第二快的此类算法（仅次于数域筛法Number Field Sieve）。对于110位以下的十位整数，它仍是最快的，而且都认为它比数域筛法更简单。
24. RANSAC——是“RANdom SAmple Consensus”的缩写。该算法根据一系列观察得到的数据，数据中包含异常值，估算一个数学模型的参数值。其基本假设是：数据包含非异化值，也就是能够通过某些模型参数解释的值，异化值就是那些不符合模型的数据点。
25. RSA——公钥加密算法。首个适用于以签名作为加密的算法。RSA在电商行业中仍大规模使用，大家也相信它有足够安全长度的公钥。
26. Sch?nhage-Strassen算法——在数学中，Sch?nhage-Strassen算法是用来完成大整数的乘法的快速渐近算法。其算法复杂度为：O(N log(N) log(log(N)))，该算法使用了傅里叶变换。
27. 单纯型算法（Simplex Algorithm）——在数学的优化理论中，单纯型算法是常用的技术，用来找到线性规划问题的数值解。线性规划问题包括在一组实变量上的一系列线性不等式组，以及一个等待最大化（或最小化）的固定线性函数。
28. 奇异值分解（Singular value decomposition，简称SVD）——在线性代数中，SVD是重要的实数或复数矩阵的分解方法，在信号处理和统计中有多种应用，比如计算矩阵的伪逆矩阵（以求解最小二乘法问题）、解决超定线性系统（overdetermined linear systems）、矩阵逼近、数值天气预报等等。
29. 求解线性方程组（Solving a system of linear equations）——线性方程组是数学中最古老的问题，它们有很多应用，比如在数字信号处理、线性规划中的估算和预测、数值分析中的非线性问题逼近等等。求解线性方程组，可以使用高斯—约当消去法（Gauss-Jordan elimination），或是柯列斯基分解（ Cholesky decomposition）。
30. Strukturtensor算法——应用于模式识别领域，为所有像素找出一种计算方法，看看该像素是否处于同质区域（ homogenous region），看看它是否属于边缘，还是是一个顶点。
31. 合并查找算法（Union-find）——给定一组元素，该算法常常用来把这些元素分为多个分离的、彼此不重合的组。不相交集（disjoint-set）的数据结构可以跟踪这样的切分方法。合并查找算法可以在此种数据结构上完成两个有用的操作：
    • 查找：判断某特定元素属于哪个组。
    • 合并：联合或合并两个组为一个组。
32. 维特比算法（Viterbi algorithm）——寻找隐藏状态最有可能序列的动态规划算法，这种序列被称为维特比路径，其结果是一系列可以观察到的事件，特别是在隐藏的Markov模型中。

现实中算法

Linux内核中的基本数据结构和算法

1. 链表、双向链表和无锁链表

2. B+ 树，代码中的注释将会告诉你一些教科书中不能学到的内容：

   这是一个简单的B+树实现，我写它的目的是作为练习，并以此了解B+树的工作原理。结果该实现发挥了它的实用价值。

   ...

   一个不经常在教科书中提及的技巧：最小值应该放在右侧，而不是左侧。一个节点内所有被使用的槽位应该在左侧，没有使用的节点应该为NUL，大部分的操作只遍历一次所有的槽位，在第一个NUL处终止。

3. 带权重的有序列表用于互斥锁、驱动等；

4. 红黑树用于调度、虚拟内存管理、跟踪文件描述符和目录条目等；
5. 区间树
6. Radix树，用于内存管理、NFS相关查找和网络相关的功能；

   radix树的一个常见的用法是保存页面结构体的指针；

7. 优先级堆，文字上的描述，主要是在教科书中实现，用于control group系统;

   包含指针的只允许简单插入的静态大小优先级堆，基于CLR（算法导论）第七章

8. 哈希函数，引用Knuth和他的一篇论文：

   Knuth建议选择与机器字长所能表达的最大整数约成黄金比例的素数来做乘法散列，Chuck Lever 证实了这个技术的有效性；

   http://www.citi.umich.edu/techreports/reports/citi-tr-00-1.pdf

   这些选择的素数是位稀疏的，也就是说对他们的操作可以使用位移和加法来替换机器中很慢的乘法操作；

9. 有些代码，比如这个驱动，他们是自己实现的哈希函数

10. 哈希表，用于实现索引节点、文件系统完整性检查等；
11. 位数组，用于处理flags、中断等，在Knuth第四卷中有对其特性的描述；
12. Semaphores 和 spin locks
13. 二叉树搜索用于中断处理、登记缓存查找等；
14. 使用B-树进行二叉树查找；
15. 深度优先搜索和他的变体被应用于目录配置；

    在命名空间树中执行一个修改过的深度优先算法，开始（和终止于）start_handle所确定的节点。当与参数匹配的节点被发现以后，回调函数将会被调用。如果回调函数返回一个非空的值，搜索将会立即终止，这个值将会回传给调用函数；

16. 广度优先搜索用于在运行时检查锁的正确性；
17. 链表上的合并排序用于垃圾回收、文件系统管理等；
18. 在某个驱动程序的库函数里，冒泡排序居然也被实现了

19. 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

20. 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 浏览器中的数据结构和算法

1. 伸展树

   此树会被分配策略参数化，这个策略负责在C的自由存储空间和区域中分配列表，参见zone.h

2. Demo中使用了Voronoi图
3. 基于Bresenham算法的标签管理

同时，代码中还包含了一些第三方的算法和数据结构，例如：

1. 二叉树
2. 红黑树
3. AVL树
4. 用于压缩的Rabin-Karp字符串匹配
5. 计算自动机的后缀
6. 苹果实现的布隆过滤器
7. 布氏算法

编程语言类库

1. C++ STL，包含的有列表、堆、栈、向量、排序、搜索和堆操作算法
2. Java API 非常广泛，包含的太多
3. Boost C++ 类库，包含了诸如Boyer-Moore和Knuth-Morris-Pratt字符串匹配算法等；

分配和调度算法

1. 最近最少使用算法有多种实现方式，在Linux内核中是基于列表实现的；
2. 其他可能需要了解的是先入先出、最不常用和轮询；
3. VAX、VMS系统中大量使用FIFO的变体；
4. Richard Carr的时钟算法被用于Linux中页面帧替换；
5. Intel i860处理器中使用了随机替换策略；
6. 自适应缓存替换被用于一些IBM的存储控制中，由于专利原因在PostgreSQL只有简单的应用；
7. Knuth在TAOCP第一卷中提到的伙伴内存分配算法被用于Linux内核中，FreeBSD和Facebook都在使用jemalloc并发分配器；

*nix系统中的核心组件

1. grep和awk都实现了使用Thompson-McNaughton-Yamada构建算法实现从正则表达式中创建NFA
2. tsort实现了拓扑排序
3. fgrep实现了Aho-Corasick 字符串匹配算法；
4. GNU grep，据作者Mike Haertel所说，实现了Boyer-Moore算法；
5. Unix中的crypt(1)实现了哑谜机（Enigma Machine）中的加密算法的变种；
6. Doug Mcllroy基于和James合作的原型实现的Unix diff，比用来计算Levenshtein距离的标准动态规划算法更好，Linux版本被用来计算最短编辑距离；

加密算法

1. Merkle树，尤其是Tiger Tree Hash的变种，用于点对点的程序，例如GTK Gnutella 和LimeWire;
2. MD5用于为软件包提供校验码，还用于*nix系统（Linux实现）中的完整性校验，同时他还支持Windows和OS X系统；
3. OpenSSL实现了需要加密算法，诸如AES，Blowfish，DES，SHA-1，SHA-2，RSA，DES等；

编译器

1. yacc和bison实现了LALR解析器
2. 支配算法用于基于SSA形式的最优化编译器；
3. lex和flex将正则表达式编译为NFA；

压缩和图片处理

1. 为GIF图片格式而出现的Lempel-Zivsraf算法在图片处理程序中经常被应用，从一个简单的*nix组件转化为一个复杂的程序；

2. 运行长度编码被用于生成PCX文件（用于Paintbrush这个程序中），压缩BMP文件和TIFF文件；

3. 小波压缩（Wavelet压缩）是JPEG 2000的基础，所以所有生成JPEG 2000文件的数码相机都是实现了这个算法；

4. 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。

数据结构与算法 Big O 备忘录与现实

原文：http://www.cnblogs.com/wintersun/p/4840585.html