《数据结构与算法之美》-5-字符串匹配
| 算法 | 预处理时间 | 匹配时间 |
|---|---|---|
| BF算法 / 朴素算法 | 0 (无需预处理) | Θ(nm) |
| Rabin-Karp算法 | Θ(m) | 平均 Θ(n + m),最差 Θ((n-m)m) |
| 基于有限状态机的搜索 | Θ(mk) | Θ(n) |
| 克努斯-莫里斯-普拉特算法 | Θ(m) | Θ(n) |
| Boyer-Moore字符串搜索算法 | Θ(m + k) | 最好Ω(n/m),最坏 O(n) |
| Bitap算法 | Θ(m + k) | O(mn) |
信息论
信息论（英语：information theory）是应用数学、电子学和计算机科学的一个分支，涉及信息的量化、存储和通信等。信息论是由克劳德·香农发展，用来找出信号处理与通信操作的基本限制，如数据压缩、可靠的存储和数据传输等。自创立以来，它已拓展应用到许多其他领域，包括统计推断、自然语言处理、密码学、神经生物学、进化论和分子编码的功能、生态学的模式选择、热物理、量子计算、语言学、剽窃检测、模式识别、异常检测和其他形式的数据分析。
熵是信息的一个关键度量，通常用一条消息中需要存储或传输一个符号的平均比特数来表示。熵衡量了预测随机变量的值时涉及到的不确定度的量。例如，指定掷硬币的结果（两个等可能的结果）比指定掷骰子的结果（六个等可能的结果）所提供的信息量更少（熵更少）。
