一、连加与连乘运算
1. 连加符号 (Σ)
* 符号表示：∑
* 表达式：∑i=mnai=am+am+1+⋯+an\sum_{i=m}^{n} a_i = a_m + a_{m+1} + \cdots + a_n∑i=mn ai =am +am+1 +⋯+an
* 运用场景：
* 计算序列的和
* 统计求和
* 算法中的循环累加操作
* 示例：
* ∑i=15i=1+2+3+4+5=15\sum_{i=1}^{5} i = 1 + 2 + 3 + 4 + 5 = 15∑i=15 i=1+2+3+4+5=15
* ∑k=0n2k=20+21+⋯+2n\sum_{k=0}^{n} 2^k = 2^0 + 2^1 + \cdots + 2^n∑k=0n 2k=20+21+⋯+2n
2. 连乘符号 (Π)
* 符号表示：∏
* 表达式：∏i=mnai=am×am+1×⋯×an\prod_{i=m}^{n} a_i = a_m \times a_{m+1} \times \cdots \times a_n∏i=mn ai =am ×am+1 ×⋯×an
* 运用场景：
* 计算序列的乘积
* 阶乘运算 (n! = ∏_{k=1}^n k)
* 概率中的联合概率
* 示例：
* ∏i=14i=1×2×3×4=24\prod_{i=1}^{4} i = 1 \times 2 \times 3 \times 4 = 24∏i=14 i=1×2×3×4=24
* ∏k=1n(1+1k)=n+1n\prod_{k=1}^{n} (1 + \frac{1}{k}) = \frac{n+1}{n}∏k=1n (1+k1 )=nn+1
二、幂运算与对数运算
1. 幂运算
* 符号表示：aba^bab
* 定义：a的b次方，表示a乘以自身b次
* 性质：
* am×an=am+na^m \times a^n = a^{m+n}am×an=am+n
* (am)n=am×n(a^m)^n = a^{m \times n}(am)n=am×n
* a−n=1ana^{-n} = \frac{1}{a^n}a−n=an1
* 运用场景：
* 指数增长/衰减模型
* 计算复杂度
* 密码学中的模幂运算
2. 对数运算
* 符号表示：logₐb
* 定义：如果a^x = b，那么x = logₐb
* 常用对数：
* 自然对数：ln x (以e为底)
* 常用对数：lg x (以10为底)
* 计算机科学中：log x通常指以2为底
* 性质：
* loga(mn)=logam+loganlog_a (mn) = log_a m + log_a nloga (mn)=loga m+loga n
* loga(m/n)=logam−loganlog_a (m/n) = log_a m - log_a nloga (m/n)=loga m−loga n
* loga(mn)=nlogamlog_a (m^n) = n log_a mloga (mn)=nloga m
* 换底公式：logab=logcblogcalog_a b = \frac{log_c b}{log_c a}loga b=logc alogc b
* 运用场景：
* 算法复杂度分析
* 解决指数方程
* 数据压缩和信息论
三、时间复杂度与空间复杂度
1. 时间复杂度
* 定义：算法执行所需时间与输入规模的关系
* 大O符号：表示最坏情况下的渐进上界
* 常见复杂度：
* O(1)：常数时间
* O(log n)：对数时间
* O(n)：线性时间
* O(n log n)：线性对数时间
* O(n²)：平方时间
* O(2ⁿ)：指数时间
* O(n!)：阶乘时间
* 分析方法：
* 计算基本操作的次数
* 忽略低阶项和常数因子
* 取最高阶项
2. 空间复杂度
* 定义：算法执行所需内存空间与输入规模的关系
* 分析方法：
* 计算额外使用的存储空间
* 不包括输入数据本身占用的空间
* 同样使用大O表示法
* 常见复杂度：
* O(1)：原地算法
* O(n)：线性空间
* O(n²)：平方空间
四、C++ STL容器：VECTOR
1. 概念
* 动态数组：可自动调整大小的序列容器
* 特点：
* 连续内存存储
* 随机访问O(1)时间复杂度
* 尾部插入/删除高效(O(1)均摊)
* 中间插入/删除O(n)时间复杂度
2. 基本使用
3. 迭代器使用
4. 性能与注意事项
* 优点：
* 缓存友好(连续内存)
* 动态扩容(无需手动管理内存)
* 丰富的成员函数
* 缺点：
* 中间插入/删除效率低
* 扩容可能导致迭代器失效
* 扩容策略：
* 通常按2倍或1.5倍增长
* 扩容时需要重新分配内存和拷贝元素
* 使用建议：
* 预分配足够空间(reserve)以减少扩容开销
* 优先使用emplace_back而非push_back(避免临时对象)
