分类目录归档:数学与算法

数学与算法

有限自动机的字符串匹配

自动机虽然是通过很多数学知识来论证其正确性,但是其原理确很简单。这里通过加回忆之前的学习,简单介绍下自动机的字符串匹配原理。自动机的字符在完成前期的工作后,其字符串的匹配时间复杂度为O(n),其中n为目标串的字符数,即自动机的匹配搜索不需要回溯,其如何完成避免回溯工作的呢? 继续阅读

Huffman编码的证明过程与反思

看到http://mindhacks.cn/2011/07/10/the-importance-of-knowing-why-part3/这篇文章后,突然想起自己学习败者树的经历。当时确实认为自己已经掌握了败者树的构建原理与方法。可是没有过几天,再次给别人讲解时又忘得像没有学过一样。如作者所说,我们真的没有掌握其证明过程,而只是记住结论了。 继续阅读