Suppose that pattern P and text T are randomly chosen strings of length m and n, respectively, from the d-ary alphabet Σd = {0, 1, . . . , d - 1}, where d ≥ 2. Show that the expected number of character-to-character comparisons made by the implicit loop in line 4 of the naive algorithm is
over all executions of this loop. (Assume that the naive algorithm stops comparing characters for a given shift once a mismatch is found or the entire pattern is matched.) Thus, for randomly chosen strings, the naive algorithm is quite efficient.
证明:
令P为单个字符比较匹配的概率,1-P为失配的概率,P=d-1
比较次数 概率 比较次数 * 概率
1 1 - P 1 - P
2 P(1 - P) 2P - 2P2
3 P2 (1 - P) 3P - 3P3
…
m-1 Pm-2(1 - P) (m-1)Pm-2 - (m-1) Pm-1
m Pm-1(1 - P)+Pm-1P (m)Pm-1 - (m) Pm+ (m)Pm
E =∑(比较次数 * 概率) = 1+P+P2+…..Pm-1 = (1-Pm)/1-P = (1- d –m )/( 1- d-1)
令f(x) =(1- x –m )/( 1- x-1),对f(x)求导可知,在m>1,x>=2时导数为负,则f(x)在x>=2严格减函数,所以f(x)<=f(2)<=2.证毕。
由此可知,对于随机的字符串,朴素的字符串比较还是有效的。
分享到:
相关推荐
a vague suggestion to a solution to some of the exercises posed in the book Introduction to algorithms by Cormen, Leiserson and Rivest. It is very likely that there are many errors and that the ...
中文名: 算法导论 原名: Introduction to Algorithms 作者: Thomas H. Cormen Ronald L. Rivest Charles E. Leiserson Clifford Stein 资源格式: PDF 版本: 文字版 出版社: The MIT Press书号: 978-0262033848发行...
现代农林英语-转基因植物-Reading-Exercises翻译-.doc
算法导论 CLRS Mit Press - Introduction To Algorithms 2Nd Edition Incl Exercises Edition.chm
麻省理工算法导论 Table of Contents Introduction to Algorithms, Second Edition Preface Part I - Foundations Chapter 1 - The Role of Algorithms in Computing Chapter 2 - Getting Started ...
Exercises-and-Tests-源码.rar
《算法导论》习题解答.rar Solutions for Introduction to algorithms second edition Philip Bille The author of this document takes absolutely no responsibility for the contents. This is merely a vague ...
exercises-json-rpc.pdfexercises-json-rpc.pdfexercises-json-rpc.pdfexercises-json-rpc.pdfexercises-json-rpc.pdfexercises-json-rpc.pdfexercises-json-rpc.pdfexercises-json-rpc.pdf
Chapter 3 - Growth of Functions Chapter 4 - Recurrences Chapter 5 - Probabilistic Analysis and Randomized Algorithms Part II - Sorting and Order Statistics Chapter 6 - Heapsort Chapter 7 - ...
exercises-js-master.rar
a vague suggestion to a solution to some of the exercises posed in the book Introduction to algo- rithms by Cormen, Leiserson and Rivest. It is very likely that there are many errors and that the ...
It is important that you try hard to solve the exercises on your own. Use this document only as a last resort or to check if your instructor got it all wrong. Please note that the document is under ...
算法导论第二版习题答案 英文版 Solutions for Introduction to algorithms second edition Philip Bille The author of this document takes absolutely no responsibility for the contents. This is merely a ...
Solutions_to_Exercises_and_Problems
Chapter 3 - Growth of Functions Chapter 4 - Recurrences Chapter 5 - Probabilistic Analysis and Randomized Algorithms Part II - Sorting and Order Statistics Chapter 6 - Heapsort Chapter 7 - ...
a vague suggestion to a solution to some of the exercises posed in the book Introduction to algorithms by Cormen, Leiserson and Rivest. It is very likely that there are many errors and that the ...
The only way to master matrix algebra is by working through exercises. Most texts have exercises, but few offer solutions. Harville's main text is great because it offers proofs for most theorems. ...
Pandas是入门Python做数据分析所必须要掌握的一个库,本篇精选了十套练习题以及数据文件,帮助读者上手Python代码,完成数据集探索。
ant-exercises-sklearn
Excerpt from Amazon: Some books on algorithms are ... Many new exercises and problems have been added for this edition. As of the third edition, this textbook is published exclusively by the MIT Press.