算法学习 1.1从若干实例探讨算法的思考模式.pdf

《算法学习 1.1从若干实例探讨算法的思考模式.pdf》由会员分享，可在线阅读，更多相关《算法学习 1.1从若干实例探讨算法的思考模式.pdf（62页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、从若干实例探讨算法的思考模式七月算法邹博2015年4月7日4月算法在线班2/总论 算法包罗万象 推理、逻辑、“机智”演绎、归纳、类别 算法是脑力的游戏 合理运用算法，能够获得更高的效率4月算法在线班3/机智：停车的是几号车位？4月算法在线班4/倒过来看一看4月算法在线班5/系统的“数数”围棋棋盘由横纵19*19条线组成，这些线共组成多少个正方形？思路：边长为1的正方形多少个？边长为2的呢？边长为3、4、的呢？以某个点为右下角的正方形共有多少个？然后把所有点的正方形数相加。4月算法在线班6/逻辑推理：完形填空 皇帝不是穷人，在守财奴之中也有穷人，所以，有一些_并不是_。4月算法在线班7/使用离散

2、数学分析该题目 p：这个人是皇帝 q：这个人是穷人 r：这个人是守财奴 皇帝不是穷人：pq 在守财奴之中也有穷人：x(xr xq)4月算法在线班8/分析过程 r：这个人是守财奴 p：这个人是皇帝 有一些 守财奴 并不是 皇帝。4月算法在线班9/系统：字符串表达式的计算 a+b*(c-d)+e 朴素算法 逆波兰表达式 栈的典型应用4月算法在线班10/最大连续子数组 给定一个数组A0,n-1，求A的连续子数组，使得该子数组的和最大。例如 数组：1,-2,3,10,-4,7,2,-5，最大子数组：3,10,-4,7,24月算法在线班11/最大连续子数组的解法 暴力法 分治法 分析法 动态规划法4月算

3、法在线班12/暴力法 直接求解Ai,j的值：0 i n i j n i,i+1,j-1,j的最大长度为n 因此：时间复杂度O(n3)4月算法在线班13/暴力法Code4月算法在线班14/分治法 将数组从中间分开，那么最大子数组要么完全在左半边数组，要么完全在右半边数组，要么跨立在分界点上。完全在左数组、右数组递归解决。跨立在分界点上：实际上是左数组的最大后缀和右数组的最大前缀的和。因此，从分界点向前扫，向后扫即可。4月算法在线班15/分治Code4月算法在线班16/分治法算法复杂度分析算法的递推关系：T(n)=2*T(n/2)+cn，c为常数若，则有：若2kn2k+1，则T(2k)T(n)Al

4、ow，则Alow,low+1.mid-1,mid是递增序列，最小元素位于子数组Amid+1,mid+2,high中。因此，做赋值low=mid+1；若：AmidAlow，则Alow,low+1.mid-1,mid不是递增序列，即：中间元素该子数组中，做赋值high=mid。注：对偶地，若考察Amid与Ahigh的关系，能够得到相似的结论。4月算法在线班23/代码4月算法在线班24/零子数组 求对于长度为N的数组A，求子数组的和接近0的子数组，要求时间复杂度O(NlogN)。4月算法在线班25/算法流程申请同样长度的空间sum0N-1，sumi是A的前i项和。Trick：定义sum-1=0显然有

5、：算法：对sum0N-1排序，然后计算sum相邻元素的差，最小值记为min1。min1：在A中任意取两个集合，各自元素的和求差的最小值因为sum-1=0，sum0N-1的绝对值最小值记为min2。min2：A的前k个元素的和的绝对值的最小值min1和min2的更小者，即为所求。1isumjsumAjikk4月算法在线班26/要说明的两个问题 sum本身的计算和相邻元素差的计算，都是O(N)，sum的排序是O(NlogN)，因此，总时间复杂度：O(NlogN)强调：除了计算sum相邻元素的差的最小值，别忘了sum自身的最小值。一个对应Aij，一个对应A0j4月算法在线班27/LCS的定义 最长公

6、共子序列，即Longest Common Subsequence，LCS。一个序列S任意删除若干个字符得到新序列T，则T叫做S的子序列；两个序列X和Y的公共子序列中，长度最长的那个，定义为X和Y的最长公共子序列。字符串13455与245576的最长公共子序列为455字符串acdfg与adfc的最长公共子序列为adf 注意区别最长公共子串(Longest Common Substring)最长公共字串要求连续4月算法在线班28/LCS的意义 求两个序列中最长的公共子序列算法，广泛的应用在图形相似处理、媒体流的相似比较、计算生物学方面。生物学家常常利用该算法进行基因序列比对，由此推测序列的结构、功

7、能和演化过程。LCS可以描述两段文字之间的“相似度”，即它们的雷同程度，从而能够用来辨别抄袭。另一方面，对一段文字进行修改之后，计算改动前后文字的最长公共子序列，将除此子序列外的部分提取出来，这种方法判断修改的部分，往往十分准确。简而言之，百度知道、百度百科都用得上。4月算法在线班29/暴力求解：穷举法 假定字符串X，Y的长度分别为m，n；X的一个子序列即下标序列1,2,m的严格递增子序列，因此，X共有2m个不同子序列；同理，Y有2n个不同子序列，从而穷举搜索法需要指数时间O(2m.2n)；对X的每一个子序列，检查它是否也是Y的子序列，从而确定它是否为X和Y的公共子序列，并且在检查过程中选出最

8、长的公共子序列；显然，不可取。4月算法在线班30/LCS的记号 字符串X，长度为m，从1开始数；字符串Y，长度为n，从1开始数；Xi=x1，xi即X序列的前i个字符(1im)(Xi不妨读作“字符串X的i前缀”)Yj=y1，yj即Y序列的前j个字符(1jn)(字符串Y的j前缀)；LCS(X,Y)为字符串X和Y的最长公共子序列，即为Z=z1，zk。注：不严格的表述。事实上，X和Y的可能存在多个子串，长度相同并且最大，因此，LCS(X,Y)严格的说，是个字符串集合。即：Z LCS(X,Y).4月算法在线班31/LCS解法的探索：xm=yn 若xm=yn(最后一个字符相同)，则：Xm与Yn的最长公共子

9、序列Zk的最后一个字符必定为xm(=yn)。zk=xm=yn LCS(Xm,Yn)=LCS(Xm-1,Yn-1)+xm4月算法在线班32/结尾字符相等，则LCS(Xm,Yn)=LCS(Xm-1,Yn-1)+xm 记LCS(Xm,Yn)=W+xm，则W是Xm-1的子序列；同理，W是Yn-1的子序列；因此，W是Xm-1和Yn-1的公共子序列。反证：若W不是Xm-1和Yn-1的最长公共子序列，不妨记LCS(Xm-1,Yn-1)=W，且|W|W|；那么，将W换成W，得到更长的LCS(Xm,Yn)=Wxm，与题设矛盾。4月算法在线班33/举例：xm=ynBADBCBAYABACDBX7654321对于上

10、面的字符串X和Y：x3=y3=C，则：LCS(BDC,ABC)=LCS(BD,AB)+Cx5=y4=B，则：LCS(BDCAB,ABCB)=LCS(BDCA,ABC)+B4月算法在线班34/LCS解法的探索：xmyn 若xmyn，则：要么LCS(Xm,Yn)=LCS(Xm-1,Yn)，要么LCS(Xm,Yn)=LCS(Xm,Yn-1)。证明：令Zk=LCS(Xm,Yn)；由于xmyn则zkxm与zkyn至少有一个必然成立，不妨假定zkxm(zkyn的分析与之类似)。因为zkxm，则最长公共子序列Zk是Xm-1和Yn得到的，即：Zk=LCS(Xm-1,Yn)同理，若zkyn，则Zk=LCS(Xm

11、,Yn-1)即，若xmyn，则：LCS(Xm,Yn)=maxLCS(Xm-1,Yn),LCS(Xm,Yn-1)4月算法在线班35/举例：xmynBADBCBAYABACDBX7654321对于字符串X和Y：x2y2，则：LCS(BD,AB)=max LCS(BD,A),LCS(B,AB)x4y5，则：LCS(BDCA,ABCBD)=max LCS(BDCA,ABCB),LCS(BDC,ABCBD)4月算法在线班36/LCS分析总结 显然，属于动态规划问题。nmnmnmnmmnmnmyxYXLCSYXLCSyxxYXLCSYXLCS当当1111,max,4月算法在线班37/算法中的数据结构：长度

12、数组 使用二维数组Cm,n ci,j记录序列Xi和Yj的最长公共子序列的长度。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列，故ci,j=0。jijiyxjijicjicyxjijicjijic且当且当或者当,0,01,1max,0,011,1000,4月算法在线班38/算法中的数据结构：方向变量 使用二维数据Bm,n，其中，bi,j标记ci,j的值是由哪一个子问题的解达到的。即ci,j是由ci-1,j-1+1或者ci-1,j或者ci,j-1的哪一个得到的。取值范围为Left，Top，LeftTop三种情况。4月算法在线班39/实例 X=Y=4月算法在线班40/计算LCS长度4月算法在

13、线班41/根据b提供的方向，构造最长公共子序列4月算法在线班42/算法实现Demo4月算法在线班43/进一步思考的问题 方向数组b是完全可以省略的：数组元素ci,j的值仅由ci-1,j-1，ci-1,j和ci,j-1三个值之一确定，因此，在计算中，可以临时判断ci,j的值是由ci-1,j-1，ci-1,j和ci,j-1中哪一个数值元素所确定，代价是(1)时间。若只计算LCS的长度，则空间复杂度为min(m,n)。在计算ci,j时，只用到数组c的第i行和第i-1行。因此，只要用2行的数组空间就可以计算出最长公共子序列的长度。4月算法在线班44/最大公共子序列的多解性：求所有的LCS 当xmyn时

14、：若LCS(Xm-1,Yn)=LCS(Xm,Yn-1)，会导致多解：有多个最长公共子序列，并且它们的长度相等。B的取值范围从1,2,3扩展到1,2,3,4 广度优先遍历nmnmnmnmmnmnmyxYXLCSYXLCSyxxYXLCSYXLCS当当1111,max,4月算法在线班45/LCS的应用：最长递增子序列LIS Longest Increasing Subsequence 给定一个长度为N的数组，找出一个最长的单调递增子序列。例如：给定数组 5，6，7，1，2，8，则其最长的单调递增子序列为5，6，7，8，长度为4。分析：其实此LIS问题可以转换成最长公子序列问题，为什么呢？4月算法在

15、线班46/使用LCS解LIS问题 原数组为A 5，6，7，1，2，8 排序后：A1，2，5，6，7，8 因为，原数组A的子序列顺序保持不变，而且排序后A本身就是递增的，这样，就保证了两序列的最长公共子序列的递增特性。如此，若想求数组A的最长递增子序列，其实就是求数组A与它的排序数组A的最长公共子序列。此外，本题也可以直接使用动态规划来求解4月算法在线班47/LCS的应用：最长递增子序列LIS Longest Increasing Subsequence 给定一个长度为N的数组，找出一个最长的单调递增子序列。例如：给定数组 5，6，7，1，2，8，则其最长的单调递增子序列为5，6，7，8，长度为

16、4。分析：其实此LIS问题可以转换成最长公子序列问题，为什么呢？4月算法在线班48/使用LCS解LIS问题 原数组为A 5，6，7，1，2，8 排序后：A1，2，5，6，7，8 因为，原数组A的子序列顺序保持不变，而且排序后A本身就是递增的，这样，就保证了两序列的最长公共子序列的递增特性。如此，若想求数组A的最长递增子序列，其实就是求数组A与它的排序数组A的最长公共子序列。此外，本题也可以直接使用动态规划来求解4月算法在线班49/附：LIS的动态规化算法 设长度为N的数组为a0，a1,a2,.an-1，则假定以aj结尾的数组序列的最长递增子序列长度为L(j)，则L(j)=max(L(i)+1,

17、ij且aiaj。也就是说，我们需要遍历在j之前的所有位置i(从0到j-1)，找出满足条件aiaj的L(i)，求出max(L(i)+1即为L(j)的值。最后，我们遍历所有的L(j)(从0到N-1)，找出最大值即为最大递增子序列。时间复杂度为O(N2)。4月算法在线班50/LIS4月算法在线班51/LCS与字符串编辑距离 字符串编辑距离(Edit Distance)，是俄罗斯科学家Vladimir Levenshtein在1965年提出的概念，又称Levenshtein距离，是指两个字符串之间，由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括 将一个字符替换成另一个字符 插入一个字符 删

18、除一个字符 如何求两个字符串的编辑距离？去年9月26日百度一二面试题，10月9日腾讯面试题第1小题，10月13日百度2013校招北京站笔试题第二大题第3小题，及去年10月15日2013年Google校招笔试最后一道大题皆是考察的这个字符串编辑距离问题。4月算法在线班52/编辑距离的应用DNA分析基因学的一个主要主题就是比较 DNA 序列并尝试找出两个序列的公共部分。如果两个 DNA 序列有类似的公共子序列，那么这些两个序列很可能是同源的。在比对两个序列时，不仅要考虑完全匹配的字符，还要考虑一个序列中的空格或间隙(或者，相反地，要考虑另一个序列中的插入部分)和不匹配，这两个方面都可能意味着突变(

19、mutation)。在序列比对中，需要找到最优的比对(最优比对大致是指要将匹配的数量最大化，将空格和不匹配的数量最小化)。如果要更正式些，可以确定一个分数，为匹配的字符添加分数、为空格和不匹配的字符减去分数。拼写纠错(Spell Correction)&拼写检查(Spell Checker)将每个词与词典中的词条比较，英文单词往往需要做词干提取等规范化处理，如果一个词在词典中不存在，就被认为是一个错误，然后试图提示N个最可能要输入的词拼写建议。常用的提示单词的算法就是列出词典中与原词具有最小编辑距离的词条。命名实体抽取(Named Entity Extraction)&实体共指(Entity

20、Coreference)由于实体的命名往往没有规律，如品牌名，且可能存在多种变形、拼写形式，如“IBM”和“IBM Inc.”，这样导致基于词典完全匹配的命名实体识别方法召回率较低，为此，我们可以使用编辑距离由完全匹配泛化到模糊匹配。字符串核函数(String Kernel)最小编辑距离作为字符串之间的相似度计算函数，用于SVM等机器学习算法中。4月算法在线班53/字符串编辑的分析 字符串“ALGORITHM”是如何变成字符串“ALTRUISTIC”的4月算法在线班54/递推关系枚举字符串S和T最后一个字符si、tj对应的四种情况：(字符-字符)(字符-空白)(空白-字符)(空白-空白)；显然

21、的是，(空白-空白)必然是多余的编辑操作。S+空白T+字符XS变成T，最后，在S的末尾插入“字符X”dpi,j=dpi,j-1+1S+字符XT+字符YS变成T，最后，在X修改成Ydpi,j=dpi-1,j-1+(X=Y?0:1)S+字符XT+空白S变成T，X被删除dpi,j=dpi-1,j+14月算法在线班55/编辑距离4月算法在线班56/进一步的思考 允许交换，算一次变换：如meter/metre 能否写出递推关系式？还能设计出O(n2)的算法吗？如果计算字符串的语义距离，怎么考虑？WordNet是由Princeton 大学的心理学家，语言学家和计算机工程师联合设计的一种基于认知语言学的英语

22、词典。它不是光把单词以字母顺序排列，而且按照单词的意义组成一个“单词的网络”。4月算法在线班57/应用编辑距离处理实际问题的剪枝策略 因为一般拼写检查应用只需要给出Top-N的纠正建议即可(如N=10)，那么我们可以从词典中按照长度依次为len、len-1、len+1、len-2、len+2、.的词条比较；限定拼写建议词条与当前词条的最小编辑距离不能大于某个阈值；如果搜索到最小编辑距离为x以内的候选词条超过N后，终止处理；缓存常见的拼写错误和建议，提高性能。4月算法在线班58/进一步思考 如果要计算两个已知字符串的最长公共子串的问题，如何求解？借鉴LCS的思想：求字符串A，B的最长公共子串S

23、考察A的i前缀和B的j前缀的最长公共子串S(i,j)：若Ai=Bj，则S(i,j)=S(i-1,j-1)+14月算法在线班59/附：实例 求字符串bab和caba的最长公共子串4月算法在线班60/参考文献 余祥宣等，计算机算法基础M，华中科技大学出版社，2001 刘佳梅.求最长公共子序列问题的一种快速算法.中国科技论文在线J.2010,11 李欣，舒风迪.最长公共子序列问题的改进快速算法.计算机应用研究J.2000 郑翠玲.最长公共子序列算法的分析与实现.武夷学院学报J,2010,29 卷(2):4448 https:/ 更多算法面试题在官网 http:/ 直播课程 问答社区 contact us：微博 七月算法 七月问答4月算法在线班62/感谢大家恳请大家批评指正！