算法 – 第 7 页 – JONY'S WORDPRESS

完全背包问题与多重背包问题

完全背包问题与多重背包问题完全背包问题的描述是“给定容积为\(V\)的背包与物品序列，物品\(i\)的价值与体积分别为\(A_i,B_i\)。设序列中每个物品有无限个可以取，如何取物品可使总价值最大”。《算法导论》中的钢条切割问题就是完全背包问题。这个问题本身可以转化成(01)背包问题，虽然每种物品有无限个，但背包容量却是有限的，故对于物品\(i\)，其至多能被取\(\lfloor{V/B_i}\rfloor\)次(其中\(\lfloor \rfloor\)表示向下取整，即直接丢弃小数点后的数)，从无限变为有限后就很好处理了，只需要把这些一样的物体“平铺”开就能得到一个新的物品序列，然后用这个新的物品序列求解对应的(01)背包问题即可。按上述思路可得状态转移方程\(F(k,V)=max\{~ F(i-1,V-mB_i)… 阅读全文

最大连续子序列问题

最大连续子序列之前讨论过该问题的一种分治算法，这里讨论基于另一种划分子问题策略的DP算法。设原数组\(L=[i_0,i_1,…,i_n]\)，函数\(F(k)\)为“\(L\)中以\(i_k\)结尾的全部连续子数组的元素值之和中的最大值”，则\(F(k)\)满足方程“\(F(k+1) = max\{ F(k) + L[k+1], L[k+1] \}\)，且\(F(0)=L[0]\)”。若解出\(F(0),F(1),..,F(n)\)，求出其中最大值即得原问题的解。该求解过程的编程实现通常是这样，先定义数组\(F[k]\)表示\(F(k)\)，从\(F[0]\)开始自低向高以数组递推并记录\(F[k]\)所有值，最后求数组\(F[k]\)的最大值即为解。算法代价为\(O(n)\)。上述分析与解决问题的方法就是动态规划，其中关于\(F(k)\)的方程被称为动态规划的状态转移方程。该动态规划算法的代码既简短也易理解，但其实该问题本身并不特别简单，最大子数组问题最早于1977年提出，但直到1984年才被卡内基梅隆大学的教授Jay… 阅读全文

最长公共子序列问题

最长公共子序列问题最长公共子序列(LCS)问题中LCS的定义为“对于任意两个序列\(X,Y\)，若\(Z\)为其LCS，则\(Z\)中的所有元素必然同时存在于\(X,Y\)中，且其在\(X,Y\)中的下标是递增的”。首先定义状态转移函数\(F(i,j)\)表示原问题中\(X[0…i],Y[0…j]\)子序列的LCS长度，容易得出状态转移方程如上，因为\(F(i,j)\)是单调递增的。如上图所示，在递推\(F(i,j)\)状态的同时，如果维护一个“备忘录”数组，则可利用其求出其中一个LCS，并且注意到对\(F(i-1,j)=F(i,j-1)\)的情况加以处理可求出全部LCS。下文的代码仅通过回溯状态转移数组求出其中一个LCS。 Python def dp(X,Y):… 阅读全文

最长上升子序列问题

最长LIS问题(\(O(n^2)\))最长LIS(上升子序列)问题是一个经典的动态规划问题，问题描述如下“LIS是指从左到右的排序子序列，对于任意给定序列\(L\)求出它所有上升子序列(LIS)的最大长度。例如\([1,3,9,6,8]\)的一个最长LIS是\([1,3,6,8]\)，其长度为4”。这个问题的朴素算法可以是先求出原序列的全部子集(保持原有顺序)，然后遍历判断其是否为LIS并记录长度。用\(F(k)\)表示“以\(L[k]\)结尾的最长LIS长度”。对满足\(F(k)\)的所有序列，若删去\(L[k]\)必是满足\(\{F(i) | i\in [0,k-1]\}\)中某问题的序列或空序列，且删去\(L[k]\)后的序列长度等于满足\(L[i]<L[k]\)的上述所有\(F(i)\)中的最大值。所以\(F(k)\)满足状态转移方程\(F(k)… 阅读全文

矩阵连乘的最优结合策略

矩阵连乘的最优结合 1) 结合策略：矩阵乘法满足交换律，故通常无需加括号，有\(a\times b\)矩阵\(X\)，\(b\times c\)矩阵\(Y\)，\(c\times d\)矩阵\(Z\)，朴素乘法用结合策略\((XY)Z\)的代价为\(O(abc+acd)\)，利用\(X(YZ)\)的代价为\(O(bcd + abd)\)，不同结合策略会导致不同的代价。规定待连乘的矩阵序列(下标)为\([A_1,A_2,…,A_n]\)，维度序列为\([p_0,p_1,…,p_n]\)，即\(A_i\)为\(p_{i-1} \times p_i\)矩阵； 2) 枚举法：设\(P(n)\)为\(n\)个矩阵连乘的结合(加括号)方案总数，则有\(P(n)=\sum_{k=1}^{n-1} P(k)P(n-k)\)，\(P(1)=1\)。解得\(P(n)=\Omega… 阅读全文

最优二叉搜索树问题

给定关键字的BST数目设\(L\)为包含\(n\)个关键字的元素互异的递增序列，把\(L\)可形成的所有形态的BST数目计为\(C(n)\)，然后推导\(C(n)\)的递推表达式，其核心在于按\(L\)每个元素作树根的情况划分问题，然后得出\(C(n)\)与每个根节点左右子树的\(C\)的关系并求和：第1个关键字为树根时有\(C(n-1)\)种情况，第2个关键字为树根时有\(C(n-2)\)种情况…第5个时有\(C(4)C(n-5)\)种…第k个时有\(C(k-1)C(n-k)\)种…。整理得到\(C(0) = 1\)，\(C(n+1) = \sum_{i=0}^n C(i)C(n-i)\)。\(C(n)\)被称为Catalan数，其以比利时数学家欧仁·查理·卡塔兰… 阅读全文

线性表

线性表线性表(linear list)是种非常简单的结构。一个线性表等价于一个集合与该集合所有元素的一个排序，可写成\([a,b,c,…]\)的形式，方括号中的内容既表示线性表中的全部元素，也表示这些元素的排序。对于线性表中任意前后相邻的\(x_i\)与\(x_{i+1}\)元素，通常称\(x_i\)的后继为\(x_{i+1}\)，\(x_{i+1}\)的前驱为\(x_i\)，首个元素的前驱为空，最后一个元素的后继为空。需注意到线性表本身是个逻辑概念，其不限制也不依赖于具体实现，就类似于集合这样的概念，在讨论算法时经常会遇到这种类型的概念。在算法领域人们更关心线性表的实现，因为线性表本身十分简答。实际的计算机硬件基本都采用相同的“内存模型”，其包括由确定的\(K\)个连续整数构成的\(K\)个内存地址，每个地址都存储相同规模的数据。读取内存的流程大致是先提供内存地址给内存，一段时间后内存返回该地址中的数据，写入内存的流程大致是同时提供地址和数据给内存，一段时间后内存完成写入。在这种“内存模型”下，线性表的实现方案通常是数组或链表，这两种方案都有各自的优缺点。当然如果不采用这种“内存模型”，也有一定的可能会用其他方案来实现线性表。… 阅读全文

栈与队列

栈(Stack)栈这种结构强调的是栈运算，实现了如下3种运算的结构就是栈： 1) \(push(x)\)：存入\(x\)元素(也称为压栈)； 2) \(pop()\)：删除最后一次存入的元素并返回该元素(也称为弹栈)； 3) \(top()\)：返回最后一次存入的元素(也称为栈顶，所以写作top)；直观上栈像狭长的储物箱，只有一面开口，只能看到最顶上的物品，取最里面的物品时要自顶向下的先拿出所有其他物品。这3种运算使栈中的元素在逻辑上也蕴含着前驱后继关系，所以栈也是线性表。但栈不必像数组和链表那样，必须提供查看任意元素、在任意元素间插入、删除任意元素等各种运算，所以直观上栈并不像一张“表”，而像是有3个运算的“黑箱”，所以栈也被称为操作受限的线性表。当然如果在链表或数组的基础上实现栈运算的话，那也可以作为栈。栈作为后进先出(LIFO,… 阅读全文

直接寻址表与哈希表

直接寻址表(Direct Address Table)数组是把所有元素按顺序存储在连续内存地址中的，如果单个元素需要的内存地址数越多，数组整体需要的内存地址数就要成倍增长。显然同样大小的连续内存比不连续内存更“稀缺”，因为即使有足够的内存，也不代表有足够的连续内存。那么为更合理的使用内存，在元素数量多且单个元素很大的场景下就不应直接使用大数组存储，而是应该考虑使用链表，但如果对按索引访问的性能有高的要求，就需要结合数组和链表的特点构造一种新的称为直接寻址表的结构。直接寻址表本身是个数组，但元素不存入数组，而是存入不连续的其他内存区域，数组中存储的是元素的内存地址。直接寻址表的各个位置称为槽(slot)，其允许索引不连续(索引1有元素、索引2没元素、索引3又有元素……)，所以把索引改称为关键字(key)。当元素不大时，也允许不存地址，而是依然存元素本身。所以数组可看作直接寻址表的特例，很多时候甚至不区分这两个概念，因为直接寻址表仅多了1次按地址找元素的步骤，和数组的代价是没有区别的。直接寻址表还有些其他好处，数组创建时必须确定每个元素占用的固定大小。直接寻址表就自由的多，由于其存储的只是地址，所以元素的大小可以不同。事实上很多程序语言中“基于数组”的数据类型更接近直接寻址表而不是数组，比如Python的list。… 阅读全文

摊还分析与动态表

摊还分析(Amortized Analysis) 通常算法分析的“目标问题”都是给定1个规模为\(n\)的数据结构和1个算法，分析该算法关于\(n\)的代价并表示为\(O(f(n))\)。如果在此基础上继续分析“在该数据结构连续执行\(k\)次该算法”的问题，用乘法可得\(O(kf(N))\)，其中\(N\)是\(k\)次中最大的\(n\)。由于\(O\)是上界所以该结论完全正确，但可能不够“精确”(离确界不够近)。因为没考虑到每次算法执行后，数据结构本身的变化。如果考虑到，则可能得到小于\(O(kf(N))\)的界，并且其更能反映出该场景下的真实代价。举例说明上述观点，假设有个“包含\(popAll\)运算”的栈，其除了能\(O(1)\)完成\(push,pop,top\)，还支持\(popAll\)运算，其实现是“循环\(pop\)直到栈顶为空”，如果\(popAll\)执行前栈中有\(n\)个元素，\(popAll\)的代价就是\(O(n)\)。然后带入场景“这个栈是某算法的一部分，该算法会多次调用这个栈的\(push,pop,popAll\)，由于这个算法很复杂，不能确定每次都调用什么运算，也不能确定每次调用前栈的元素数。只知道算法开始时栈是空的”。由于不知道元素数，\(popAll\)的\(O(n)\)代价就不精确了，但我们很想衡量这个栈在该算法中的性能表现，所以构造下面这个需要做算法分析的“目标问题”：… 阅读全文