2011年3月3日

算法入门----第2章 分类： 算法导论 2011-03-03 11:11 131人阅读 评论(0) 收藏

摘要： 1.算法正确性的证明数学归纳法：证明当 n = 1 时命题成立。证明如果在 n = m 时命题成立，那么可以推导出在 n = m+1 时命题也成立。（m 代表任意自然数）算法的迭代性，以及有类似归纳法的特性可以用归纳法来证明其正确性。2.插入算法。效率：/**********************... 阅读全文

posted @ 2011-03-03 11:11 Joyfulmath 阅读(156) 评论(0) 推荐(0)

String 匹配算法（2）---第32章 分类： 算法导论 2011-03-03 10:55 163人阅读 评论(0) 收藏

摘要： 3.KMP算法（Knuth-Morris-Pratt ）该算法的与Rabin-Karp一脉相承。也就是先排除可能不是的，在可能中逐一比较。I.π函数的得到：COMPUTE-PREFIX-FUNCTION(P) 1 m ← length[P] 2 π[1] ← 0 3 k ← 0 4 for q ← ... 阅读全文

posted @ 2011-03-03 10:55 Joyfulmath 阅读(184) 评论(0) 推荐(0)

String 匹配算法---第32章 分类： 算法导论 2011-03-03 10:43 193人阅读 评论(0) 收藏

摘要： 1.navite string 算法：基本就是一个一个匹配，对于不太长的字串来说，效率还行。效率：O((n - m + 1)m)算法伪代码：NAIVE-STRING-MATCHER(T, P)1 n ← length[T]2 m ← length[P]3 for s ← 0 to n - m4 ... 阅读全文

posted @ 2011-03-03 10:43 Joyfulmath 阅读(149) 评论(0) 推荐(0)

导航