归档/Math & Coding数据结构与算法2026/5/10Math & Coding# 数据结构与算法数据结构与算法 引言 关键词 数据结构 算法 大O表示法 卡特兰数 通项公式（闭合式）： Cn=1n+1(2nn)=(2n)!(n+1)!n!C_n = \frac{1}{n+1} \binom{2n}{n} = \frac{(2n)!}{(n+1)!n!}Cn=n+11(n2n)=(n+1)!n!(2n)! 递推公式（动态规划常用）： C0=1，Cn=∑i=0n−1Ci×Cn−1−i(n≥1)C_0 = 1，C_n = \sum_{i=0}^{n-1} C_i \times C_{n-1-i} \quad (n \ge 1)C0=1，Cn=∑i=0n−1Ci×Cn−1−i(n≥1) 线性递推公式（计算效率最高）：C0=1，Cn=2(2n−1)n+1Cn−1C_0 = 1，C_n = \frac{2(2n-1)}{n+1} C_{n-1}C0=1，Cn=n+12(2n−1)Cn−1 共享栈 中缀表达式 后缀表达式 前缀表达式