L7 - 算法优化与高效问题求解

🎯 教学目标

  1. 掌握时间复杂度分析方法，能估算程序性能并优化算法
  2. 熟练应用前缀和技巧，解决区间统计类问题
  3. 深入理解二分法，实现查找与答案判定双重功能
  4. 构建递归思维模型，学会用记忆化搜索优化重复计算

📚 核心知识体系

一、时间复杂度分析（理论基石）

1
2
3
4
5
6
7
8
9
// 示例：比较两种算法的耗时差异
void algo_O_n(int n) {  // O(n)
    for(int i=0; i<n; i++) { /* 操作 */ }
}

void algo_O_n2(int n) { // O(n²)
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++) { /* 操作 */ }
}

复杂度对比表

数据规模 O(n)（毫秒） O(n²)（毫秒）
n=1e3 1 1000
n=1e4 10 100000

二、前缀和与差分数组（区间处理利器）

1. 一维前缀和模板

1
2
3
4
5
vector<int> preSum(nums.size()+1, 0);
for(int i=0; i<nums.size(); i++) 
    preSum[i+1] = preSum[i] + nums[i];

// 查询区间[a,b]和：preSum[b+1] - preSum[a]

2. 二维前缀和应用

1
2
3
// 矩阵区域和计算
sum = preSum[x2][y2] - preSum[x1-1][y2] 
      - preSum[x2][y1-1] + preSum[x1-1][y1-1];

三、二分法双模式（查找与答案判定）

1. 经典二分查找

1
2
3
4
5
6
7
8
9
10
int binarySearch(vector<int>& nums, int target) {
    int left=0, right=nums.size()-1;
    while(left <= right) {
        int mid = left + (right-left)/2;
        if(nums[mid] == target) return mid;
        if(nums[mid] < target) left = mid+1;
        else right = mid-1;
    }
    return -1;
}

2. 二分答案框架

1
2
3
4
5
6
7
8
9
int findMaxValue(int maxLimit) {
    int left=0, right=maxLimit;
    while(left < right) {
        int mid = (left + right + 1) >> 1; // 取右中位数
        if(check(mid)) left = mid;  // check函数验证答案可行性
        else right = mid-1;
    }
    return left;
}

四、递归与记忆化搜索（性能飞跃）

1. 递归三要素实现

1
2
3
4
int fibonacci(int n) {
    if(n <= 1) return n;                // 终止条件
    return fibonacci(n-1) + fibonacci(n-2); // 递归公式
}

2. 记忆化搜索优化

1
2
3
4
5
6
unordered_map<int, int> memo;
int fibMemo(int n) {
    if(n <= 1) return n;
    if(memo.count(n)) return memo[n];
    return memo[n] = fibMemo(n-1) + fibMemo(n-2);
}

性能对比

算法 计算fib(40)时间 时间复杂度
普通递归 ＞60秒 O(2ⁿ)
记忆化搜索 ＜1毫秒 O(n)

🧩 综合应用案例

山脉数组查找目标值（融合二分与递归）

1
2
3
4
5
6
7
8
9
int findInMountainArray(int target, MountainArray &mountainArr) {
    // 步骤1：二分查找峰值点
    int peak = findPeak(mountainArr);
    // 步骤2：左半区升序二分
    int leftRes = binarySearch(mountainArr, 0, peak, target, true);
    if(leftRes != -1) return leftRes;
    // 步骤3：右半区降序二分
    return binarySearch(mountainArr, peak+1, mountainArr.length()-1, target, false);
}

🏋️ 配套训练体系

1. 时间复杂度分析训练

题目1：基础复杂度判定

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 请分析以下代码的时间复杂度
void func1(int n) {
    int a = 0;
    for(int i=0; i<1000; i++) a++;
}

void func2(int n) {
    for(int i=0; i<n; i+=2) 
        printf("%d", i);
}

void func3(int n) {
    for(int i=1; i<=n; i*=2)
        for(int j=0; j<i; j++) 
            printf("*");
}

题目2：算法对比决策
假设计算机每秒处理1e6次操作，当n=1e5时：

  • 算法A：时间复杂度O(n√n)，需要预处理1秒
  • 算法B：时间复杂度O(n²)，无需预处理
    应选择哪个算法？给出数学依据

2. 前缀和实战题单

题目1：子数组异或查询（LeetCode 1310）
» 给定数组，处理多个查询[i,j]，返回从i到j的异或结果
» 关键技巧：利用异或前缀性质preXor[j+1] ^ preXor[i]

题目2：航班预订统计（LeetCode 1109）
» 处理n个航班的预订记录[first, last, seats]，返回每日座位数
» 核心解法：差分数组+前缀和还原

题目3：最大子矩阵（LeetCode 面试题17.24）
» 给定二维矩阵，找出元素和最大的子矩阵
» 高阶技巧：二维前缀和压缩+一维最大子数组转化

3. 二分法专项训练

题目1：寻找峰值（LeetCode 162）
» 数组可能包含多个峰值，返回任意一个峰值的索引
» 思维突破：比较mid与mid+1决定搜索方向

题目2：H指数 II（LeetCode 275）
» 给定学者论文被引次数的升序数组，计算其H指数
» 判定条件设计：citations[mid] >= n - mid

题目3：分割数组的最大值（LeetCode 410）
» 将数组分割为m个连续子数组，最小化最大子数组和
» 答案二分法典型应用：验证给定最大值是否可行

4. 记忆化搜索挑战

题目1：带障碍的路径统计（LeetCode 63 改编）
» 网格中存在障碍物，求从左上角到右下角的路径数（允许→和↓移动）
» 进阶条件：若路径必须经过某特定点，如何修改记忆化策略

题目2：硬币组合问题（LeetCode 518 改编）
» 给定不同面额的硬币和总金额，求凑成金额的硬币组合数
» 空间优化：如何将二维记忆化压缩为一维DP

题目3：正则表达式匹配（LeetCode 10）
» 实现支持.和*的正则表达式匹配
» 记忆化技巧：用哈希表记录(i,j)位置的匹配结果

🧑💻 训练指导建议

  1. 复杂度分析：使用主定理处理递归式，对比不同阶的增长曲线图
  2. 前缀和题单：先手算推导矩阵区域和公式，再转化为代码实现
  3. 二分训练：所有题目先用闭区间写法实现，再改为左闭右开对比差异
  4. 记忆化搜索：先用树状图分析递归展开过程，再添加记忆化剪枝

📝 学习路径导图