理论计算机科学速查表：定义、数列与重要公式概览

理论计算机科学速查表提供了数学公式总结，对于理解和应用该领域的核心概念非常实用。以下是部分内容的详细解析： 1. **定义与上界/下界表示法**: - `f(n)=O(g(n))` 表示函数 `f(n)` 的增长速度上限是 `g(n)` 的一个常数倍，即存在正实数 `c` 和 `n0`，当 `n` 大于等于 `n0` 时，`f(n)` 的值不大于 `cg(n)`。 - `f(n)=Ω(g(n))` 表示 `f(n)` 的增长速度下限也是 `g(n)` 的一个常数倍，即存在正实数 `c` 和 `n0`，`f(n)` 不小于 `cg(n)` 对所有 `n` 大于等于 `n0` 成立。 - `f(n)=Θ(g(n))` 是上界和下界的结合，意味着 `f(n)` 同时是 `O(g(n))` 和 `Ω(g(n))`。 2. **数列与级数**: - 累加公式展示了几种常见数列的求和形式，如前 `n` 项和，例如 `n*(n+1)/2` 对于平方数序列，`n*(n+1)*(2n+1)/6` 对于立方数序列。 - 一般情况下，有限项和和无限项几何级数的公式，如 `c^(n+1)-1/(c-1)` 和 `c/(1-c)` 分别适用于 `c` 不等于1的情况。 - 阶乘数列和组合数的表示，如 `n!` 和组合公式 `C(n,k) = n! / (k!(n-k)!)`。 3. **特殊数列**: - 求和形式的调和级数 `H_n` 包括部分和的递推关系以及渐近性质，如 `H_n = 1 + 1/2 + 1/3 + ... + 1/n`，其部分和有特定的递推关系。 4. **极限与最值**: - `lim` 表示极限运算，用于定义函数在某点的值或序列的趋向。例如 `lim n→∞ an = a` 表示随着 `n` 趋于无穷大，`an` 趋向于 `a`。 - `sup` 和 `inf` 分别表示集合中的上确界（最大值）和下确界（最小值），这对于理解序列和函数的行为至关重要。 5. **组合论**: - 提供了计算大小为 `k` 的从大小为 `n` 的集合中取出子集的组合数的公式 `C(n,k)`，以及斯特林数，它们在算法设计和组合优化中扮演着角色。 这个速查表将理论计算机科学中的数学基础和关键概念汇总在一起，帮助学习者快速掌握和记忆重要的公式和定义，对于深入理解和解决复杂问题具有极大的便利性。无论是处理时间复杂度分析、算法设计还是数据结构中的问题，这些公式都是必不可少的工具。