明德 A 班第 17 次课课堂笔记

Algor

2025-05-09 13:26:12

发布于：广东

9阅读

0回复

0点赞

一、连加与连乘运算

1. 连加符号 (Σ)

符号表示：∑
表达式： $\sum_{i=m}^{n} a_i = a_m + a_{m+1} + \cdots + a_n$
运用场景：
- 计算序列的和
- 统计求和
- 算法中的循环累加操作
示例：
- $\sum_{i=1}^{5} i = 1 + 2 + 3 + 4 + 5 = 15$
- $\sum_{k=0}^{n} 2^k = 2^0 + 2^1 + \cdots + 2^n$

2. 连乘符号 (Π)

符号表示：∏
表达式： $\prod_{i=m}^{n} a_i = a_m \times a_{m+1} \times \cdots \times a_n$
运用场景：
- 计算序列的乘积
- 阶乘运算 (n! = ∏_{k=1}^n k)
- 概率中的联合概率
示例：
- $\prod_{i=1}^{4} i = 1 \times 2 \times 3 \times 4 = 24$
- $\prod_{k=1}^{n} (1 + \frac{1}{k}) = \frac{n+1}{n}$

二、幂运算与对数运算

1. 幂运算

符号表示： $a^b$
定义：a的b次方，表示a乘以自身b次
性质：
- $a^m \times a^n = a^{m+n}$
- $(a^m)^n = a^{m \times n}$
- $a^{-n} = \frac{1}{a^n}$
运用场景：
- 指数增长/衰减模型
- 计算复杂度
- 密码学中的模幂运算

2. 对数运算

符号表示：logₐb
定义：如果a^x = b，那么x = logₐb
常用对数：
- 自然对数：ln x (以e为底)
- 常用对数：lg x (以10为底)
- 计算机科学中：log x通常指以2为底
性质：
- $log_a (mn) = log_a m + log_a n$
- $log_a (m/n) = log_a m - log_a n$
- $log_a (m^n) = n log_a m$
- 换底公式： $log_a b = \frac{log_c b}{log_c a}$
运用场景：
- 算法复杂度分析
- 解决指数方程
- 数据压缩和信息论

三、时间复杂度与空间复杂度

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. 基本使用

#include <vector>
using namespace std;

// 创建vector
vector<int> v1;              // 空vector
vector<int> v2(5);           // 5个元素，默认初始化
vector<int> v3(5, 10);       // 5个元素，每个初始化为10
vector<int> v4 = {1,2,3,4};  // 初始化列表

// 访问元素
int first = v4[0];           // 下标访问(不检查边界)
int second = v4.at(1);       // 带边界检查的访问
int front = v4.front();      // 第一个元素
int back = v4.back();        // 最后一个元素

// 修改内容
v4.push_back(5);             // 尾部添加元素
v4.pop_back();               // 删除尾部元素
v4.insert(v4.begin()+1, 10); // 在指定位置插入
v4.erase(v4.begin()+2);      // 删除指定位置元素
v4.clear();                  // 清空所有元素

// 容量操作
bool isEmpty = v4.empty();   // 判断是否为空
size_t size = v4.size();     // 当前元素数量
v4.resize(10);               // 调整大小
size_t cap = v4.capacity();  // 当前容量
v4.reserve(100);             // 预分配空间

3. 迭代器使用

// 遍历vector
for(auto it = v4.begin(); it != v4.end(); ++it) {
    cout << *it << " ";
}

// 范围for循环(C++11)
for(int num : v4) {
    cout << num << " ";
}