算法与数据结构

White...约 4575 字大约 15 分钟

哈夫曼编码是一种一致性编码, 又称熵编码法, 用于数据的无算耗压缩。

逆波兰式, 也叫后缀表达式, 是将运算符写在操作数之后的表示方法。对逆波兰式求值的方法是从左至右扫描表达式, 遇到操作数则压栈, 遇到运算符号则从栈中弹出操作数进行运算, 然后将结果压入栈中, 重复该过程直至表达式结束, 最后栈顶的元素即为结果。

二维数组

将二维数组元素存储到存储器中有两种主要技术：

按行存储：二维数组的所有行连续地存储在存储器中。
按列存储：二维数组的所有列都连续地存储在存储器中。

如下的二维数组中, arr[M,N]指一个 M 行 N 列的二维数组：

(0,0)	(0,1)	(0,2)
(1,0)	(1,1)	(1,2)
(2,0)	(2,1)	(2,2)

按照行主顺序的存储, 数组的第一行完全存储到存储器中, 然后数组的第二行完全存储到存储器中, 直到最后一行也完全存储到存储器, 即： $(0,0),(0,1),(0,2),(1,0),(1,1),(1,2),(2,0),(2,1),(2,2)$
按照列主顺序的存储, 数组的第一列完全存储到存储器中, 然后数组的第二列完全存储到存储器中, 直到数组的最后一列, 即： $(0,0),(1,0),(2,0),(0,1),(1,1),(2,1),(0,2),(1,2),(2,2)$

练习

若二维数组 arr[1..M, 1..N] 的首地址为 base, 数组元素按列存储且每个元素占用 K 个存储单元, 则元素 arr[i,j] 在该数组空间的地址为（C）。

A. $base+((i-l) \times M+j-1) \times K$
B. $base+((i-l) \times N+j-l) \times K$
C. $base+((j-l) \times M+i-l) \times K$
D. $base+((j-l) \times N+i-l) \times K$

分析：M 行 N 列, 一列有 M 个元素, 一行有 N 个元素, arr[i,j]是第 i 行第 j 个元素

按行的地址：前面有i-1行的是排满的, 也就是(i-1)N个元素, 剩下j-1个, 得到 $(i-1)N+(j-1)+base$
按列的地址：前面有j-1列的是排满的, 也就是(j-1)M个元素, 剩下i-1个, 得到 $(j-1)M+(i-1)+base$

树的遍历：先序（根左右）、中序（左根右）、后序（左右根）

数据挖掘就是应用一些列技术从大型数据库或数据仓库中提取人们感兴趣的信息和知识, 这些知识或信息是隐含, 事先未知而潜在有用的, 提取的知识表示为概念、规则、规律、模式等形式。也就是说数据挖掘是一类深层次的数据分析。常见和应用最广泛的数据挖掘方法如下：

决策树：决策树方法是利用信息论中的互信息（信息增益）寻找数据库中具有最大信息量的属性字段, 建立决策树的一个结点, 再根据该属性字段的不同区直建设书的分支；在每个分支子集中重复建立树的下层结点和分支的过程。国际上最早的、最有影响的决策树方法是 Quiulan 研究的 ID3 方法。
神经网络：神经网络方法是模拟人脑的神经元结构, 完成类似统计学中的判断、回归、聚类等功能, 是一种非线性的模型, 主要有三种神经网络模型：前馈式网络、反馈式网络和自组织网络。
遗传算法：遗传算法是模拟生物进化过程的算法, 他由三个基本过程组成：繁殖（选择）、交叉（重组）、变异（突变）。采用遗传算法的可以产生优良的后代。经过若干代的遗传, 将得到满足要求的后代即问题得解。
关联规则挖掘算法：关联规则是描述数据之间存在关系的规则, 形式为"A1A2A3...An => B1B2B3...Bn"。一般分为两个步骤, 求出最大数据项集、用大数据项集缠身关联规则。
除上述常用方法外, 还有粗集方法, 模糊集合方法, Bayesian Belief Netords, 最邻近算法（K-nearest Neighbors Method, KNN）等。

二分查找

对于数组 A[1..n], 查找关键字 key 使用二分查找法的步骤：1.先计算中间位置下标mid；2.若要查找的关键字key<A[mid], 说明要找的对象在A[1]~A[mid-1]之间, 同理, 若要查找的关键字key>A[mid], 说明要找的对象在A[mid+1]~A[n]之间；3.重复上述步骤直至成功找到结果或失败为止。

根据二分查找过程中的关键字序列构造二分查找树判定树：如果根为空, 则当前元素为根；比根小的放左边, 比根大的放右边；如果左子树不为空, 重复上述步骤。

练习

对 n 个元素的有序表 A[1...n]进行二分查找（除 2 取商时向下取整）, 查找元素 A[i]时, 最多与 A 中的（）个元素进行比较。

解答：第一次二分 n/2, 第二次二分 n/2/2..., 第 m 次二分 n/2^m, 最坏情况下排除完只剩下一个元素, 得到 $n/2^m=1$ , 可以得到 $log2(n)=m$ , 所以二分查找的时间复杂度为 log2(n), 此时再与最后一个元素进行比较得到 log2(n)+1

对于循环队列, 求队头元素的指针的计算公式为：

(rear-len+1+M)\%M

求队列中元素个数（长度）公式为（其中 front 指队头指针）：

(rear-front+M)\%M

栈和队列是两种常用的数据结构。栈的特点是后进先出, 队列的特点是先进先出。因此入队序列和出队序列一定相同, 而入栈序列和出栈序列不一定相同。

栈和队列都是操作首先的线性表：栈仅在表尾插入和删除元素, 队列仅在表头删除元素, 在队尾插入元素。

线性表进行顺序存储时, 逻辑上相邻的元素, 其物理位置也相邻。在已知第一个元素存储位置和元素序号的情况下, 可以计算出任意元素的存储位置, 即按照序号访问元素是随机的, 该运算的时间复杂度为 O(1)；而插入元素时需要移动一些元素, 因此该运算的时间复杂度为 O(n), 其中 n 是线性表的长度。

线性表进行链式存储时, 逻辑上相邻的元素物理位置上不要求相邻, 以此需要额外的存储空间表示元素之间的顺序关系。在链表上查找和插入元素的时间复杂度都为 O(n)。

对有向无环图进行拓扑排序的方法如下：

在 AOV 网中选择一个入读为零（没有前驱）的定点且输出它
从网中删除该顶点 v 以及与该顶点有关的所有边
重复上述两步, 直至网中不存在入读为零的顶点为止。

二叉树：

完全二叉树：除最后一层外, 每一层上的节点数均达到最大值；在最后一层上只缺少右边的若干结点。
平衡二叉树（AVL）：是空树, 或者左子树和右子树的深度差值不超过 1 且它的左子树和右子树都是平衡二叉树。
最优二叉树：哈夫曼树
满二叉树：每一层上的节点数均达到最大值。

哈夫曼树：是指权值为 w1, w2, ..., wn 的 n 个叶子节点的二叉树中带权路径长度最小的二叉树。树的带权路径长度为树中所有叶子节点的带权路径长度之和。

在有向图中, 若以顶点表示活动, 用有向边表示活动之间的优先关系, 则称这样的有向图为以顶点表示活动的网（Activity On Vertex Network, AOV 网）。

若在带权有向图 G 中以顶点表示事件, 以有向边表示活动, 边上的权值表示该活动持续的时间, 则这种带权有向图称为用边表示活动的网（Activity On Edge Network, AOE 网）, 通常在 AOE 网中列出了完成预定工程计划所需进行的活动、每项活动的计划完成时间、要发生哪些事件以及这些事件和活动时间的关系, 从而可以分析该项工程是否实际可行并估计工程完成的最短时间, 分析出哪些活动是影响工程进度的关键。进一步可以进行人力、物力的调度和分配, 以达到缩短工期的目的。

根据生成树的定义, 有 n 个顶点的联通图的生成树中恰好有 n-1 条边。

平均查找长度：对 n 个元素的有序列表进行顺序查找, 其成功查找的平均查找长度是(n+1)/2, 当查找的元素是第 1 个元素时进行 1 次比较, 当查找的是第 2 个元素时进行 2 次比较, ..., 当查找的是第 n 个元素时进行 n 次比较, 所以平均查找长度为(1+2+3+...+n)/n

删除一个包含 n 个元素的有序线性表中的某一个元素, 若采用顺序存储时, 删除某个元素平均需要移动(n-1)/2个元素；若采用单链表存储, 不需要移动元素（因为插入和删除都是对指针的操作）。

二叉排序树, 将新节点插入儿茶排序树时, 需要先查找插入位置。若等于树根, 则不再插入, 偌大于树根, 则递归地在右子树上查找插入位置, 否则递归地在左子树查找插入位置, 因此新结点总是叶子的方式加入树中。这样, 在根结点到达每个叶子的路径上, 结点的顺序必须保持, 也就是父结点必定先于子结点进入树中。

对于无向图中的两个顶点 u 和 V, 若存在边(u,v), 则该边为计算 U 的度和 V 的度各贡献一个值 1, 因此所有顶点的读书之和为 e 的两倍。

邻接矩阵的定义, 行列数都为结点个数。

无向边的邻接矩阵是一个对称矩阵, 每条边会表示两次, 因此矩阵中的非零元素数目为 2x 边数

有向边的邻接矩阵的每个非零元素都表示一条边, 所以非零元素数目为边数

实现函数或过程的递归调用及返回处理时必须用栈。

在 m 阶 B-树的定义中, 要求：

树中每个节点之多有 M 棵子树
若根节点不是叶子节点, 则至少两两棵子树
除根之外的所有非终端节点至少有[M/2]棵子树

图的遍历是指对图中所有顶点进行访问且只访问一次的过程。

深度优先遍历方法：从顶点 V 出发, 依次从 V 出发搜索 V 的任意一个邻接点 W；若 W 未被访问过, 则从该点出发继续深度优先遍历。类似于树的前序遍历。

广度优先遍历方法：从顶点 V 出发, 访问与顶点 V 邻接的全部未访问的顶点 W、X、Y...；然后再依次访问 W、X、Y...的邻接未访问的顶点。引入队列来保存已访问过的顶点序列。

分治法：把同一个问题拆分成多个小规模的相同子问题, 一般可用递归解决
动态规划法：划分子问题（最优子结构）, 并把子问题结果使用数组保存, 利用查询子问题结果构造最终问题的结果
贪心法：局部最优, 但整体不一定最优。每步有明确的、既定的策略
回溯法：系统搜索一个问题所有解或任一解。有试探和回退的过程。

HASH 表的装填因子表示哈希表的装满程度。装填因子越大, 冲突可能性越高。

各种排序算法对比

类别	排序方法	时间复杂度		空间复杂度	稳定性
类别	排序方法	平均情况	最坏情况	辅助存储	稳定性
插入排序	直接插入	O(n^2)	O(n^2)	O(1)	稳定
插入排序	Shell排序	O(n^1.3)	O(n^2)	O(1)	不稳定
选择排序	直接选择	O(n^2)	O(n^2)	O(1)	不稳定
选择排序	堆排序	O(nlog2(n))	O(nlog2(n))	O(1)	不稳定
交换排序	冒泡排序	O(n^2)	O(n^2)	O(1)	稳定
交换排序	快速排序	O(nlog2(n))	O(n^2)	O(log2(n))	不稳定
归并排序		O(nlog2(n))	O(nlog2(n))	O(n)	稳定
基数排序		O(d(r+n))	O(d(r+n))	O(r+n)	稳定

插入排序：将待排序的数组分为已排好序的和未排好序的两部分, 每次从未排好序的部分取出一个元素, 按从后往前的顺序依次与已排好序的部分进行比较并将其插入正确的位置, 直至所有元素均已排序。

递归推导式的方法：

代入法
递归树法
主方法

主方法

设 a≥1 和 b ＞ 1 为常数, 设 f(n) 为一函数, T(n) 由递归式T(n)=aT(n/b)+f(n)对非负整数定义, 其中 n/b 指「n/b|或|n/b」。那么 T(n)可能有如下渐进界：

若对于某常数 ε ＞ 0, 有 f(n)=O(n^logb(a-ε)), 则T(n)=Θ(n^logb(a))
若 f(n)=Θ(n^logb(a)), 则T(n)=Θ(n^logb(a)lgn)
若对于某常数 ε ＞ 0, 有f(n)=Ω(n^logb(a+ε)), 且对常数 c ＜ 1 与多有足够大的 n, 有 af(n/b)≤cf(n), 则 T(n)=Θ(f(n))

赫夫曼编码压缩比：先计算出需要二进制编码的位数 n, 然后构造赫夫曼树, 得出每个编码的长度, 计算公式：

\text{赫夫曼编码压缩比} = \frac {SUM(\text{原编码长度} \times \text{编码所占比例})} {SUM(\text{赫夫曼编码} \times \text{编码所占比例})}

练习

已知某个文档包含 5 个字符, a：40%, b：10%, c：20%, d：16%, e：14%, 则文档的压缩比为多少?

解答:
采用二进制编码, 5 个字符需要 3 位二进制( $2^3=8>5$ ), 即每位占 3bit, 平均字符长度为 $3 \times 40\%+3 \times 10\%+3 \times 20\%+3 \times 16\%+3 \times 14\%=3$ ;
采用赫夫曼编码时各编码长度分别为 1, 3, 3, 3, 3, 平均字符长度为 $1 \times 40\%+3 \times 10\%+3 \times 20\%+3 \times 16\%+3 \times 14\%=2.2$ , 所以压缩比为 $(3-2.2)/3 = 27\%$

如何构造赫夫曼树：
选取数组中值最小的两个数, 左小右大构造一颗二叉树, 将其结果替换数组中的这两个数, 再从数组中选出两个最小的数构造二叉树, 依次类推。赫夫曼编码是基于贪心法策略的。

矩阵连乘

输入连乘矩阵的个数, 每个矩阵的维数。要求输出数乘次数最少时加括号的方式, 及数乘次数。

次数：A 是一个 p×q 的矩阵, B 是一个 q×r 矩阵, AB 相乘, 得到的矩阵元素个数为 p×r, 每个元素由 q 次乘法得到, 因此所需乘法次数为 p×q×r。在计算矩阵连乘积时, 加括号的方式对计算量有影响。

例如有三个矩阵, A1、A2、A3 连乘, 它们的维数分别为 10×100, 100×5, 5×50
用第一种加括号方式 (A1A2)A3 计算, 所需数乘次数为 10×100×5+10×5×50=7500
用第二种加括号方式 A1(A2A3) 计算, 所需数乘次数为 10×100×50+100×5×50=75000

首先, 建立递归关系, 写出递归公式:

m[i,j] = \left\{ \begin{matrix} 0, & i = j\\ \underset{i \le k \lt j}{min}(m[i,k] + m[k + 1,j] + p_{i-1}p_kp_j), & i < j \end{matrix} \right.

公式解释: 假设 $k$ 是对矩阵链 $A[i:j]$ 一分为二得到最优解时的断开位置, 则 $m[i,k]$ 和 $m[k+1,j]$ 分别是两个子矩阵链 $A[i,k]$ 和 $A[k+1,j]$ 的最优解。两个矩阵最后要相乘才能得到 $A[i,j]$ , 因此, 最后要加上 $p_{i-1}p_kp_j$ , 也就是两个子矩阵相乘的数乘次数, 才能得到总的数乘次数

练习

用上述公式计算

A1(10\times100), A2(100\times5), A3(5\times50), p[]=\{10,100,5,50\}

i \ j	1	2	3
1	0	5000	7500
2		0	25000
3			0

$m[1,1]=m[2,2]=m[3,4]=0$
$m[1,2]=m[1,1]+m[2,2]+p_0p_1p_2=0+0+10\times100\times5=5000$
$m[2,3]=m[2,2]+m[3,3]+p_1p_2p_3=0+0+100\times5\times50=25000$
$m[1,3]=\left\{\begin{matrix}m[1,1]+m[2,3]+p0p1p3=0+25000+10\times100\times50=75000,&k=1\\m[1,2]+m[3,3]+p0p2p3=5000+0+10\times5\times50=7500,&k=2\end{matrix}\right.$ , 应取最小值 7500

昵称

邮箱

网址

按正序
按倒序
按热度

算法与数据结构

预览: