数据结构 & 算法

Posted on 2019-12-09 In Basic Symbols count in article: 9.7k Reading time ≈ 9 mins.

数据结构与算法是程序员的基本功, 在这个技术爆炸的时代掌握好算法能以不变应万变

himg

数据结构

内存可以理解为一个存储柜有密密麻麻的小抽屉, 每个小抽屉有一个编号 (内存地址)

数组

一种连续的多元素存储形式. 使用数组的形式存储意味着元素在内存中必定是相连的.

如果有四个相连元素以数组形式存储在内存中, 现在要将一个元素插入到第二位置, 那么原来的后三位元素必须全部向后挪动位置.

优点: 由于位置相连, 每个元素有固定的内存地址, 可使用 O(n) 时间查找出元素

缺点: 不能方便的插入与删除

链表

链表 也是一种元素在内存中的存储形式, 其存储位置可以为内存中的任何角落, 不需要相连. 每一个元素的存储信息里有本元素的信息, 同时还有下一个元素的位置信息.

优点: 可以快速插入删除, 如果要在已存储的元素之间插入一个新元素, 只需要将本元素的地址存储进入前一个元素中即可.

缺点: 不能快速查找, 如果要查找 链表 的最后一个元素, 需要计算所有的元素地址!(如果需要读取整个 链表 的所有元素, 那么 链表 速度还是可以的,
但是如果只是想读取其中某一个元素, 那么速度确实很低)

散列表 (哈希表)

如果要从一个数组中查找一个元素, 使用简单查找会检查每一个元素是否与此元素匹配, 复杂度为 O(n), 如果使用二分查找 (要求必须是顺序的数组)
则会每次从数组中间划分检查进行大小比较以确认元素是否有匹配值, 复杂度为 O(log n). 但是如果使用散列表的话在输入的瞬间立刻就能得到结果, 复杂度为 O(1)

散列表使用散列函数将输入映射到数字. 散列函数是散列表数据结构中最为关键的.

数据存储步骤

数据”milk”被输入到散列函数中
经过散列函数的计算输出结果 0
将牛奶放入到数组的索引 0 处
在下一次想找”milk”数据时同样输入到散列函数中, 经过计算返回索引值, 直接得到数据, 无需查找.

himg

散列表冲突

实际上散列表的数据并不总是存储在数组上, 因为那样的话会需要一个无穷大的数组. 因此如果一个数组预设了 26 个.
之后的每个数据会根据散列函数的计算按照字母顺序进行排列. 那么如果有 Apple 被存储到了第一个位置, 然后再有一个 avocado 需要存储的话就会发生冲突.

所以, 在有两个键映射到了同一个位置的时候就会在这个位置存储一个链表

特点

散列函数知道数组有多大, 只会返回有效的索引值. 如果数组只有五个元素, 不会返回索引值 100
散列函数会将不同输入映射到不同的索引
相对的, 散列函数会将相同的输入映射到相同的索引
目前各个语言都会提供散列函数, 不需要自己实现
一个好的散列函数能使数组的填装因子 (充满度) 保证在 0.6 左右, 一旦填装因子超过 0.7, 就该调整散列表的长度
在网页存储中很多图片或文件都是依靠 URL 进行识别下载的, 因为缓存量很大 (几万或几十万上百万), 因此为了加快索引速度在缓存中大量使用了散列表的概念,
缓存结果与对应的 URL 匹配, 在有一个 URL 需要进行请求之前会先判断此 URL 在本地散列表中是否存在, 如果存在直接根据散列函数返回的内存地址进行读取,
加载缓存取消网络请求任务达到加快访问速度的目的.
散列表最好的情况是将键均匀地映射到散列表的不同位置, 这与散列函数的好坏有关
散列表非常适合用于模拟映射关系及防止重复

栈 (Last In First Out, LIFO)

栈可以理解为一个羽毛球筒, 新元素总是会进入到最上方, 然后取出的时候总是从最上方的一个元素弹出, 即 后进先出

在编译过程中所有的函数调用都是基于栈的形式. 栈是内存的基本存储结构. 递归函数 调用的方式既是栈的典型

栈的基本操作就是 pop 和 push

队列 (First In First Out, FIFO)

队列与栈的概念相悖, 其形式与现实中的排队类似, 排队只能排至最后, 而且必须等前方队伍进行完毕才能轮到自己

有入队与出队

图

图由节点和边组成. 一个节点可能与多个节点直接相连, 这些节点被称为邻居. 图用于模拟不同的东西是如何相连的.

有向图: 两个箭头之中的边有方向

无向图: 没有方向, 等价于双向箭头的图 ( 无向图 也叫 环 )

himg

树

所有边的方向均为单向且同向

himg

二叉树

二叉树是树的一种特殊形式. 顾名思义, 这种树的每个节点最多有 2 个孩子节点, 可能有一个, 也可能没有子节点

满二叉树(Perfect Tree): 一个二叉树的所有非叶子节点都存在左孩子与右孩子, 并且所有叶子节点都在同一层级, 那么这个树就是满二叉树
完全二叉树(Complete Tree): 满二叉树要求所有分支都是满的, 二完全二叉树只需保证最后一个节点之前的节点都齐全即可
二叉查找树: 左子树上所有节点的值均小于根节点的值; 右子树上所有节点的值均大于根节点的值; 左右子树各自也都是二叉查找树

二叉堆

二叉堆本质上是一种完全二叉树, 它分为两种类型:

最大堆: 任何一个父节点的值, 都大与或等于他左孩子或右孩子节点的值
最小堆: 任何一个父节点的值, 都小于或等于他左孩子或右孩子节点的值

二叉堆是实现堆排序以及优先队列的基础

优先队列

最大优先队列: 无论入队顺序如何, 都是当前最大元素优先出队
最小优先队列: 无论入队顺序如何, 都是当前最大元素优先出队

相关概念

大 O 表示法

大 O 表示法的根本含义指的是操作数的增加速度. 衡量一个算法的好坏是使用时间复杂度与空间复杂度来进行表示的.

时间复杂度

时间复杂度公式为 T(n) = O(f(n)), f(n) 表示每行代码执行次数之和, O 表示正比例关系, 这个公式全称为 算法的渐进时间复杂度

例如:

for i in 0..< n {
    j = i
    j += 1
}

其中第 1 行运行一次, 第 2 行和第 3 行各运行 n 次, 第 4 行尾括号 (可省略), 因此总次数为 2n + 1 次, 那么总时间即为 T(n) = (2n + 1) * 颗粒时间,
通常情况下系数均可省略, 因此直接简化为 T(n) = O(n)

算法的实际消耗时间

列表包含 n 个元素, 某算法需要执行 n² 次运算得出结果, 用大 O 表示法来表示其运行时间为 O(n²). 大 O 表示法比较的是操作数, 并不是时间.

算法的总消耗时间量 = c * n²

c 是每次运算固定的时间量, 可能是 1 秒, 或者是 1 小时. n² 表示运行次数. 一般来说不会考虑常量 c, 以为对于 二分查找 的 O(log n) 和 选择排序 的
O(n²) 来说他们的差距是天壤之别, 常量 c 的影响很小. 但是在某些情况下 c 还是有作用的, 比如两个算法的运行速度都为 O(n²), 此时 c
的大小对速度影响很大.

最糟情况 & 平均情况

以快速排序为例, 因为此算法的基准值选择极为关键, 如果每次划分数组选择的基准值都是最大值或者最小值, 那么每层都涉及到 O(n) 个元素, 一共有 O(n) 层,
因此算法速度为 O(n²). 这种情况很少, 少的就像中彩票一样.

如果每次选择的基准值都位于中间, 那么将一共有 O(log n) 层, 每层涉及到 O(n) 个元素, 算法速度为 O(n * log n), 这种情况是最常见的.

常见误区

一般说算法的速度指的并非是时间, 而是指时间复杂度, 即操作数的增速
O(log n) 比 O(n) 快, 当需要搜索的元素越多时, 前者比后者快得越多
算法运行时间全部用大 O 表示法来表示

常用的时间复杂度

常数阶 O(1)
1
2
3
4
5
int i = 1;
int j = 2;
++i;
j++;
int m = i + j;
这样的代码没有循环结构, 他消耗的时间并不随着某个变量的增长而增长, 因此这样的代码无论有几千万行, 其时间复杂度都为 O(1)
线性阶 O(n)
1
2
3
4
for i in 0..< n {
j = i
j += 1
}
for 循环中的代码会执行 n 遍, 消耗的时间会随着 n 变化而变化, 这种代码均使用 O(n) 表示时间复杂度
对数阶 O(logN)
1
2
3
4
int i = 1
while (i < n) {
i = i * 2;
}
while 循环中, 每次都将 i 乘以 2, i 与 n 的距离会以指数速度减少, 即 2 的 n 次方, 换做对数即为 log2n, 因此时间复杂度为 O(logN)

时间复杂度为对数阶的常见算法有二分查找
线性对数阶 O(nlogN)
1
2
3
4
5
6
for(m=1; m<n; m++) {
i = 1;
while(i<n) {
i = i * 2;
}
}
将时间复杂度为 O(logN) 的一个代码循环 n 遍, 其时间复杂度即为 O(nlogN)
平方阶 O(n^2)
1
2
3
4
5
6
for(x=1; i<=n; x++) {
for(i=1; i<=n; i++) {
j = i;
j++;
}
}
将时间复杂度为 O(n) 的代码在嵌套循环一次, 其时间复杂度即为 O(n²)

时间复杂度为平方阶的常见算法有选择排序

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

一般时间复杂度到了 2^n 及更大的时间复杂度, 这样的算法我们基本上不会用了, 太不实用了. 比如递归实现的汉诺塔问题算法就是 O(2^n)

平方阶 ( n^2 ) 的算法是勉强能用, 而 nlogn 及更小的时间复杂度算法那就是非常高效的算法了.

空间复杂度

就像时间复杂度不是计算消耗时间的 (而是计算时间增速的), 对应的空间复杂度也不是计算消耗内存的, 而是空间消耗随 n 增长的增速

简言之, 空间复杂度即体现的是空间开辟的速度

S(n) = O(f(n))

常用空间复杂度

O(1)
1
2
3
4
5
int i = 1;
int j = 2;
++i;
j++;
int m = i + j;
算法执行的空间不随着变量 n 的大小变化, 因此算法空间复杂度为 O(1)
O(n)
1
2
3
4
5
6
int[] m = new int[n]
for(i=1; i<=n; ++i)
{
j = i;
j++;
}
这段代码中, 第 1 行构造了一个数组, 数据占用的大小为 n, 下面的 2~6 行中虽然有循环, 但是并没有分配新的空间, 而只是在原来的空间上进行赋值,
因此这段代码的空间复杂度看第一行即可, 即 S(n) = O(n)

常用排序算法的时间复杂度及空间复杂度

排序方法	稳定性	时间复杂度 (平均)	时间复杂度 (最好)	时间复杂度 (最坏)	空间复杂度
冒泡排序	稳定	O(n^2)	O(n)	O(n^2)	O(1)
选择排序	不稳定	O(n^2)	O(n^2)	O(n^2)	O(1)
插入排序	稳定	O(n^2)	O(n)	O(n^2)	O(1)
希尔排序	不稳定	O(n^1.25)	O(n^)	O(n^2)	O(1)
快速排序	不稳定	O(nlogn)	O(nlogn)	O(n^2)	O(logn)
归并排序	稳定	O(nlogn)	O(nlogn)	O(nlogn)	O(n)
堆排序	不稳定	O(nlogn)	O(nlogn)	O(nlogn)	O(1)
计数排序	稳定	O(n+k)	O(n+k)	O(n+k)	O(n+k)
桶排序	稳定	O(n)	O(n)	O(n)	不确定
基数排序	稳定	O(n*k)	O(n*k)	O(n*k)	O(n*k)

各种重复类型

循环 Loop

重复执行一段代码. 是最基础的概念, 指所有重复的行为, 迭代, 遍历, 递归都可以称之为循环

迭代 Iterate

顺序访问线性结构 (数组, 队列) 的每一项. 例如: for 语句

迭代时, 每次都会根据原变量推出一个他的新值.

遍历 Traversal

按照规则访问非线性结构的每一项

按照一定规则访问树形结构 (树, 图) 中的每一个节点, 而且每一个节点只访问一次, 典型的是树的遍历. 也可以理解为遍历一个结构的所有节点, 使每个节点都只访问一次

深度优先遍历
- 前序遍历
  
  先访问根节点, 再遍历左子树, 再遍历右子树; 因为根节点位于前侧, 因此称为前序遍历
  
  结果: [1, 2, 4, 5, 7, 8, 3, 6]
- 中序遍历
  
  先遍历左子树, 再访问根节点, 再遍历右子树; 因为根节点位于中部, 因此称为中序遍历
  
  结果: [4, 2, 7, 5, 8, 1, 3, 6]
- 后序遍历
  
  先遍历左子树, 再遍历右子树, 再访问根节点; 因为根节点位于最后, 因此称为后序遍历
  
  结果: [4, 7, 8, 5, 2, 6, 3, 1]
广度优先遍历 (层次遍历)

即每层自左至右依次输出

结果: [1, 2, 3, 4, 5, 6, 7, 8]

递归 Recursion

一个函数不断调用自身的行为

递归与普通循环的最本质区别在于递归是循环自己本身, 而普通循环只是循环一小部分.

在编写 递归函数 时, 最重要的就是编写 递归条件 和 基线条件. 基线条件 保证 递归函数 可以正常结束, 递归条件 决定 递归函数 的循环方式.

比起使用其他循环方式, 递归的性能没有优势, 但是胜在更加清晰明了

常见的算法问题

背包问题

一个贪婪地小偷, 背着可装 35kg 重量的背包, 现在有如下商品:

物品	价格	重量
音响	$3000	30 kg
笔记本电脑	$2000	20 kg
吉他	$1500	15 kg

如何才能再背包中装尽可能价值高的商品.

八皇后问题

八皇后问题是一个古老而著名的问题, 是回溯算法的典型例题. 该问题是十九世纪著名的数学家高斯 1850 年提出: 在 8X8 格的国际象棋上摆放八个皇后 (棋子),
使其不能互相攻击, 即任意两个皇后都不能处于同一行, 同一列或同一斜线上.

himg

八皇后问题也可以称之为 N 皇后问题, 解决这个问题需要用到回溯算法

NP 完全问题

需要计算所有的解, 并从中选出最小 / 最短的那个解. 但是常规算法基本不可能适用于含有大量元素的 NP 完全问题. 只能通过贪婪算法求出近似解

旅行商问题

一位旅行商要去 5 个城市, 同时想确保总旅程最短, 为此可能有几种选择?

当有两个城市时, 有 2 种选择, 当有三个城市时, 有 6 种选择, 四个城市时, 24 中选择, 这是一个阶乘问题, 当有 10 个城市时总的选择有 3628800 种选择,
这样的问题使用常规算法几乎无解. 但是可以通过 贪婪算法 取得近似解, 不过结果不是最优解.

集合覆盖问题

现在有一个广播节目, 要选择广播台以让全美 50 州的听众都收听得到. 由于每个广播台都会覆盖部分区域, 而且广播台播出要支付等价费用, 因此要选出尽可能少的广播台.

如果使用常规的算法可以穷举所有可能的集合, 如果电台数量为 n, 那么可能的子集就有 2ⁿ 个, 因此运行时间为 O(2ⁿ), 随着电台数量的增加, 其操作数将会激增.

因此这种算法不现实, 目前这种问题如果想要求得最优解是无法完成的, 但是如果只是想求得近似解, 那么可以使用贪婪算法.

NP 完全问题的特点如下:

对于 NP 完全问题, 目前还没有找到快速解决方案.
对于 NP 完全问题, 最佳的做法是使用近似算法

算法分类

排序算法

himg

选择排序 Selection Sort

himg

问题

输入 n 个无序的数字, 需要返回由这 n 个数字按顺序排列的数组.

选择排序解决思路

第一次, 从所有元素中取出最大的一个, 放入到另一个新数组中, 然后从旧数组中删除此最大元素, 第二次, 与第一次相同, 比较→取出→删除. 一直重复, 一共进行 n 次计算

算法复杂度

由于有 n 个元素, 每取出一个元素时进行了 n 次计算, 因此复杂度为 O(n²). (其实每次取出一个元素后总元素会依次变少, 到最后一次的时候只剩下了一个元素,
这涉及到大 O 运行时间的表示方法, 其忽略常数, 严格来说应该为 O(n² + n) / 2) )

快速排序 Quick Sort

himg

快速排序属于 D&C 算法, divide and conquer. 中文理解是 分而治之

一个农场主要将一块农场均匀地分成正方块, 而且分出的正方块要尽可能大. 以农场的短边进行划分出一个正方形, 然后再从剩下的农场的短边划分出另一个正方形,
重复, 直至农场的长边是短边的整数倍. 此时短边的边长即为整个农场所能划分的最大等大正方形.

问题

对一个无序数组进行排序

解决思路

从数组中随意选出一个元素作为基准值
通过大小比较将所有数组分为大于基准值和小于基准值的两个数组
重复步骤 2, 将两侧数组各选择基准值. 元素个数为 1 或 0 的数组不需要进行选择

基线条件: 数组的元素个数为 0 或 1

算法复杂度

在最糟情况 (每次选择的基准值为最大或最小) 下, 快速排序的运行时间为 O(n²), 但是在平均情况 (选择的基准值正好中等大小) 下为 O(n * log n)

冒泡排序 Bubble Sort

himg

插入排序 Insertion Sort

himg

希尔排序 Shell Sort

himg

归并排序 Merge Sort

himg

堆排序 Heap Sort

himg

计数排序 Counting Sort

himg

桶排序 Bucket Sort

himg

基数排序 Radix Sort

himg

拓扑排序

himg

拓扑排序步骤

himg

从图中选择一个没有前驱 (即入度为 0) 的顶点并输出.
从图中删除该顶点和所有以它为起点的有向边.
重复 1 和 2 直到当前图为空或当前图中不存在无前驱的顶点为止. 后一种情况说明有向图中必然存在环.

最终得到的结果为 [1, 2, 3, 4, 5]

拓扑排序特点

拓扑排序的图必须是有向无环图
树一定可以转化为拓扑图, 但是拓扑图未必可以转化为树

查找算法

二分查找

二分查找是一种简单的算法, 其输入是一个有序的元素列表 (必须是有序的列表), 如果查找的元素位于列表中, 算法会返回其位置或布尔值.

具体实现

给定一个数组, 每次将数组中央的数字取出与给定数字比较, 根据大小的比较结果进一步将范围减半, 直至得出结果.

特点

列表必须有序
算法复杂度为 O(log n)

回溯算法

回溯法 (back tracking)(探索与回溯法) 是一种选优搜索法, 又称为试探法, 按选优条件向前搜索, 以达到目标. 但当探索到某一步时,
发现原先选择并不优或达不到目标, 就退回一步重新选择, 这种走不通就退回再走的技术为回溯法, 而满足回溯条件的某个状态的点称为”回溯点”.

回溯法可以理解为通过选择不同的岔路口寻找目的地, 一个岔路口一个岔路口的去尝试找到目的地. 如果走错了路, 继续返回来找到岔路口的另一条路, 直到找到目的地.

回溯算法是解决 N 皇后问题的主要手段

广度优先搜索 BFS

himg

BFS 是从根节点开始, 沿着树 (图) 的宽度遍历树 (图) 的节点. 如果所有节点均被访问, 则算法中止.

广度优先搜索是一种用于图的查找算法, 可帮助找到两种问题的答案:

从节点 A 出发, 有无前往 B 的路径
从节点 A 出发, 前往节点 B 的哪条路径最短

搜索步骤

首先将根节点放入队列中.
从队列中取出第一个节点, 并检验它是否为目标. 如果找到目标, 则结束搜寻并回传结果. 否则将它所有尚未检验过的直接子节点加入队列中.
若队列为空, 表示整张图都检查过了, 即图中没有欲搜寻的目标. 结束搜寻并回传”找不到目标.
重复步骤 2.

按照此步骤对上图进行广度优先搜索则最终结果是 1->2->3->4->5->6->7->8

特点

广度优先搜索一般用队列来实现
广度优先搜索实现较复杂, 但是可以自己控制队列的长度
可在多条可行路径中找出最短路径

深度优先搜索 DFS

himg

深度优先搜索是沿着树的深度遍历树的各个节点, 尽可能深的搜索一个方向的所有节点, 以找到目标节点

搜索步骤

访问顶点 a;
依次从 a 的未被访问的邻接点出发, 对图进行深度优先遍历; 直至图中和 a 有路径相通的顶点都被访问;
若此时图中尚有顶点未被访问, 则从一个未被访问的顶点出发, 重新进行深度优先遍历, 直到图中所有顶点均被访问过为止.

按照此步骤对上图进行深度优先搜索则最终结果是 1->2->4->8->5->3->6->7

特点

一般用栈来实现
容易编写 (使用递归), 易于理解, 常数时间开销较小
深度优先搜索说白了就是一条路走到黑, 因此不能找到最短路径

问题

在关系网中查找芒果经销商

himg

解决思路

首先从 一级关系网 的朋友中 检索 是否有芒果经销商, 如果没有则将其标记为 已检索, 然后将朋友的朋友 ( 二级关系网 ) 以 队列 的形式加入到待搜索列表中, 等待 检索.

特点

面临类似寻找最短路径问题是, 尝试使用图来建立模型, 在使用广度优先搜索来解决问题
无向图的边不带箭头, 但是不代表没有方向, 而且方向是双向的
搜索列表必须是队列, 只有是队列类型才能保证按顺序进行检索, 才能保证检索的结果是最短路径.
对于检查过的元素, 务必不要再去检查, 否则会导致无限循环.
广度优先搜索 得出的结果是 最少节点路径, 如果需要查找 最短距离路径, 需要使用到 迪克斯特拉算法

迪克斯塔拉算法

基于图, 查找最短距离路径

问题

找出从起点到终点最短的距离

himg

解决思路

找出离起点最短的节点 A 与 B, 即可在最短时间内到达的节点
检索 A 节点的邻居的开销, 如果找到邻居节点的 自起点总开销 比之前更小则更新为 较小值
重复这个过程
最后计算最终路径并比较出最短距离路径

特点

广度优先搜索 用于在非加权图中查找 最少节点路径
迪克斯特拉算法 用于在加权图中查找 最短距离路径
仅当 图 中的所有权重为正时迪克斯特拉算法才管用
如果 图 中包含负权边, 请使用 贝尔曼 - 福德算法

贪婪算法

贪婪算法就是每步都选择最优解, 最终结合到一起得到的就是最优解.

但是在某些特殊情况下未必有效, 比如背包问题,
如果第一步透了 $3000 的音响, 后续不能再装任何东西, 但是如果不选择音响, 剩下的两件物品价值总和 $3500 超过了 $3000. 此时贪婪算法得到的结果并不是最优解.

问题

集合覆盖问题

解决思路

选择一个覆盖最多尚未被覆盖州的广播台, 即使这个广播台覆盖了一些已覆盖的州, 也没有关系.
重复第一步, 知道没有州没被覆盖.

特点

本质是通过寻找局部最优解, 企图以这种方式获得全局最优解
所得出的解只是近似解, 但是算法速度比较快
一般是用来解决常规算法很棘手的问题

K 最近邻算法 (K-Nearest Neighbours)

K 最近邻算法用于创建分类系统. 通过使用毕达哥拉斯公式以选定的特征作为因子进行计算得出距离以判断某个对象的分类. 距离反映了两个对象之间的相似程度.

himg

区分特殊点

himg

毕达哥拉斯公式

如果对一个对象选择了 5 个特征 (喜剧片, 动作片, 生活片, 恐怖片, 爱情片), 那么计算公式就变味了

himg

这时在数学家看来就是一个五维问题了

特点

为对象挑选合适的特征是最关键的影响准确因素之一, 如果通过让用户给一只小猫打分来判断其是否喜欢恐怖片, 无疑是不准确的.
回归就是预测数字
特征抽取意味着将物品转换为一系列可比较的数字
能否挑选合适的特征是 KNN 算法成功关键

应用

OCR: 机器浏览大量的数字图像, 将这些数字的特征提取出来, 遇到新图像时提取其特征, 通过 K 最近邻法找出最近的邻居的谁. 一般来说数字的特征包括 线段, 点, 曲线 等

邮件过滤系统: 常用的有 朴素贝叶斯分类器. 前期进行大量训练, 通过对垃圾邮件关键字进行分析, 来判断新邮件是否是垃圾邮件.

二叉查找树

是树的形状, 对于其中的每个节点, 左子节点的值都比它小, 右子节点的值都比他大

himg

如果要查找 maggie, 先检查根节点, 因为 maggie 大于 david, 因此向右子节点查找, 因为 maggie 小于 manning, 所以向左查找, 最终顺利找到.
整个过程与 二分查找 极为类似. 二叉查找树 的查找, 删除, 插入都比较稳定, 运行时间都为 O(log n).

数据库和高级数据结构还涉及到: B 树, 红黑树, 堆, 伸展树.

傅里叶变换

傅里叶变换能分析给定数据并返回其中所包含的成分. 比如给定一首歌曲, 傅里叶变换能将其中的各种频率分离出来

傅里叶变换非常适用于处理信号. 应用场景有:

强化低音, 隐藏高音
压缩音乐
压缩 JPG
地震预测
DNA 分析

并行算法

如果要在算法结构上进行优化改进其速度可能需要花费几年, 届时计算机速度就会更快. 现在计算机普遍采用多核计算,
因此可以设计并行算法使多个核心同时执行算法以极大地提高算法的运算速度.

分布式算法

在并行算法只需要 2-4 核时, 完全可以在普通计算机上正常运行, 但是如果上升到数百个核心, 这个时候就需要用分布式算法了, MapReduce 是一种著名的分布式算法.

MapReduce 算法使用了映射函数与归并函数. 映射函数的作用是将任务分配给多个计算机核心以便其执行, 归并函数的作用是将结果进行合并成总结果.

SHA (secure hash algorithm, sha)

使用 SHA 函数, 输入字符串会返回散列值 (字符串唯一则值唯一), 在比较大型文件时非常有用.

Gmail 的密码使用了 SHA 函数 的映射值, 在其服务器中存储的是散列值, 在输入密码后, Google 会将用户输入的密码用 SHA 函数 计算,
并将计算结果与数据库中存储的映射值作比较. SHA 函数 是单向的. 因此如果黑客攻击了 Google 的服务器拿到了所有的映射值也是没有用处的.

目前 SHA 算法 有 SHA-0, SHA-1, SHA-2, SHA-3, 越新型的越安全. 目前最安全的密码散列函数是 bcrypt

反向索引

大量用在网页搜索引擎中, 将网页中的 关键字 提取出来放入散列表中, 键 为 关键字, 值 为 页面.