基于马尔科夫链的算法复杂度分析

《基于马尔科夫链的算法复杂度分析》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、大连理工大学硕士学位论文基于马尔科夫链的算法复杂度分析姓名：王洪波申请学位级别：硕士专业：基础数学指导教师：王毅20070622大连理工大学硕士学位论文摘要字符串查找是计算机科学中基础的问题，涉及到文本编辑、数据检索、符号操作、搜索引擎等．算法复杂度是衡量算法运行效率的一把尺子，对算法的复杂度的分析是研究算法的重要课题．本文利用了马尔科夫链理论对经典字符串搜索算法KMP算法和初等算法的复杂度做了精确的刻画．文章安排如下：1．第一章主要介绍了字符串匹配算法和算法复杂度的一些知识．2．第二章描述了K

2、MP算法和初等算法．3．第三章对我们要使用的工具马尔科夫链理论做了相关的说明．4．第四章给出了分析的过程和得到的主要结果．关键词：算法复杂度；马尔科夫链；字符串匹配；KMP算法基于马尔科夫链的算法复杂度分析AnalysisofalgorithmsbasedonMarkovChinsmodelAbstractStringMatchingisafundamentalcomponentofcomputerscience，includingtextediting，dataretrieval，symbol

3、manipulation，searchingengineandSOon．Algorithmcoin-ple五tyisarulertomeasurerunningefficiencyofprogram．Somanycomputerscientistsareinterestedinthistopic．Inthispaper，WestudytheMarkovchainmodelontheautomatontailoredtotext，andderiveexactanalysisfortheaverag

4、ecaseperformanceofthebrute-forceandKMPalgorithm．TheorganizationofthispaperiSasfollows：1．Inthefirstchapter，wereviewthebackgroundandsomerelateddefinitionsofstringmatchingandalgorithmcomplexity．2．Inthesecondchapter，thetwoclassicalgorithmsaredescribed．3．

5、ThethirdchaptermainlydiscussessometheoryrelatedtoMarkovchains．4．Thelastchapterthenconsidersanalysisofalgorithmspresented，inwhichtwomaintheoremsarederived．Keywords：Analysisofalgorithms；MarkovChains；Stringmatching；KMPII独创性说明作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研

6、究工作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。作者签名：立』堕照日期：玉掣大连理工大学硕士学位论文大连理工大学学位论文版权使用授权书本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文版权使用规定’，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和电子版，允许论文

7、被查阅和借阅．本人授权大连理工大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论文．作者签名；导师签名：叫耳日大连理工大学硕士学位论文1绪论1．1字符串匹配算法字符串匹配算法是处理在一段文本tit2⋯k中搜索一个子串pip2⋯p。的一类算法．它是计算机科学中最常用的算法之一．常用的匹配算法有：1．初等算法．最原始的算法，利用穷举完成搜索匹配，时间复杂度为o(n2)．2．KMP算法．由D．E．Knuth与V．R．Pratt和J．H．Mor

8、ris【9】这三个人于1977年共同发现，因此称之为KMP算法．这是第一个在线性时间O(n+m)内完成匹配的算法．3．BM算法和BMH算法．同样在1977年，由Boyer和Moore[2]提出了BM算法．通过对BM算法的改进，Horspool

9、81在1980年得到了BMH算法，这种算法更加简单，效率却不逊色于BM算法．4．其它算法．如利用了Hash技巧f7】的Karp-Rabin算法[10]等与本文无关，在此不做详细介绍．本文只对初始算法和KMP算法的复杂度进行分析。1．2算法分析同一问题可用不