算法设计与分析

福尔摩斯上线！

（又在猜题当赌狗了！ GPT聊天链接：https://chatgpt.com/c/6febb36f-ea01-45e7-9775-ac51a2f6f545

复习PPT暂时无法在飞书文档外展示此内容\

第一章基础知识

算法复杂度概念

时间复杂度：算法执行所需时间随输入规模的增长而增长的速率。
空间复杂度：算法在执行过程中所需存储空间随输入规模的增长而增长的速率。

渐近记号O、Ω、H的含义

大O记号（O）：表示算法的上界，描述了在最坏情况下算法的运行时间或空间需求。
大Ω记号（Ω）：表示算法的下界，描述了在最优情况下算法的运行时间或空间需求
大Θ记号（Θ）：表示算法的上下界，描述了在平均情况下算法的运行时间或空间需求。

最好、最坏、平均时间（空间）复杂度

最好情况复杂度：算法在输入规模最小或输入最有利情况下的复杂度。
最坏情况复杂度：算法在输入规模最大或输入最不利情况下的复杂度。
平均情况复杂度：算法在所有可能输入情况下的平均复杂度。

分析复杂度的主要步骤，各步骤的要点

明确算法：清楚算法的步骤和流程。
确定基本操作：找到算法中最常执行的操作，作为计算复杂度的基准。
估算操作次数：根据输入规模，估算基本操作的执行次数。
简化表达式：将复杂的表达式简化为渐近记号表示的形式。
验证分析：通过实际测试或理论验证来确认复杂度的正确性。

定积分近似求和，主定理、递归树方法求解递归方程

定积分近似求和：将离散的求和问题转换为连续的积分问题，通过计算定积分来近似求和。
主定理：用于求解形如T(n) = aT(n/b) + f(n)的递归关系，具体形式如下：
- 如果f(n) = O(n^c)且c < log_b(a)，则T(n) = Θ(n^log_b(a))。
- 如果f(n) = Θ(n^c)且c = log_b(a)，则T(n) = Θ(n^c log n)。
- 如果f(n) = Ω(n^c)且c > log_b(a)，则T(n) = Θ(f(n))。
递归树方法：通过构建递归树来分析递归关系的复杂度。递归树的每个节点表示一次递归调用，树的深度和每层节点的总和决定了递归的时间复杂度。具体步骤包括：
- 画出递归树：将递归方程逐层展开，画出递归树。
- 计算每层的代价：估算递归树每层节点的总和。
- 求和所有层的代价：将所有层的代价加总，得到整个递归的复杂度。

第二章分治法

二分查找改进：通过代数变换减少子问题个数利用预处理减少递归内部计算量\

快速排序
选择问题
n-1次多项式在全体2n次方根上的求值

PPT重点题目

第三章动态规划

3.1 适用范围：子问题的最优解能推出总问题的最优解，子问题不是独立的3.2 基本步骤：直接五步走可以吗经典例题：

投资问题

问题描述：给定一定的资金，可以投资到多个项目中，每个项目有不同的收益，求资金的最佳分配，使收益最大化。算法思路：将问题转化为0-1背包问题，其中资金是背包的容量，每个项目是物品，项目的收益是物品的价值，项目的成本是物品的重量。伪代码：

输入: 资金(背包容量) M，项目成本（物品重量） cost[n]，项目收益（物品价值） profit[n]
输出: 最大收益
定义: dp = 一维数组，大小为 M+1，初始化为 0
过程:
    for i 从 1 到 n:      // 先遍历背包
        for j 从 M 到 cost[i]:    // 再遍历物品重量
            dp[j] = max(dp[j], dp[j - cost[i]] + profit[i])
返回 dp[M]

背包问题

问题描述：给定一个背包的最大容量和一系列物品，每个物品有重量和价值，求如何选择物品使得总价值最大。算法思路：经典0-1背包问题。伪代码：先遍历物品再遍历背包容量【倒序遍历】

输入: 背包容量 W，物品重量数组 weight[n]，物品价值数组 value[n]
输出: 最大价值
定义: dp = 一维数组，大小为 W+1，初始化为 0
过程: for i 从 1 到 n:
        for j 从 W 到 weight[i]:
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
返回 dp[W]

最长公共子序列LCS

问题描述：给定两个序列，求它们的最长公共子序列的长度。算法思路：使用二维数组来记录子问题的解。伪代码：

输入: 序列 X[m] 和 Y[n]
输出: 最长公共子序列的长度
定义: dp = 二维数组，大小为 (m+1) x (n+1)，初始化为 0
过程: for i 从 1 到 m:
        for j 从 1 到 n:
            if X[i-1] == Y[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
返回 dp[m][n]

图像压缩

问题描述：给定一个图像矩阵，求通过某种压缩方式后的最优结果。算法思路：可以使用动态规划来优化图像的分块处理，降低压缩的代价。伪代码：

输入: 图像矩阵 image[m][n]
输出: 最优压缩结果
定义:dp = 二维数组，大小为 (m+1) x (n+1)，初始化为 0
过程:for i 从 1 到 m:
        for j 从 1 到 n:
            dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + image[i-1][j-1]
返回 dp[m][n]

最大字段和

问题描述：给定一个整数数组，求数组中连续子数组的最大和。算法思路：使用动态规划求解，记录当前子数组的最大和。伪代码：

输入: 整数数组 nums[n]
输出: 最大子段和
定义:dp = 一维数组，大小为 n，初始化为 nums[0]
过程:max_sum = nums[0]
    for i 从 1 到 n-1:
        dp[i] = max(nums[i], dp[i-1] + nums[i])
        max_sum = max(max_sum, dp[i])
返回 max_sum

PPT重点题目

函数 MinimizeMaxProcessingTime(tasks)
    n = length(tasks)
    total_time = sum(tasks)
    half_time = total_time // 2
    
    // 初始化 dp 数组
    dp = array of size (half_time + 1) with all false
    dp[0] = true
    
    // 动态规划填表
    for i = 0 to n - 1 do
        for j = half_time down to tasks[i] do
            dp[j] = dp[j] or dp[j - tasks[i]]
    
    // 找到最大可行的 j，使得 dp[j] 为 true
    for j = half_time down to 0 do
        if dp[j] == true then
            best_time = j
            break
    
    // 计算结果
    min_time = max(best_time, total_time - best_time)
    return min_time

输入: 作业数组 tasks，每个作业有加工时间 t(i) 和效益值 v(i)，以及最大允许时间 D
输出: 最大总效益值

定义:
  dp = 一维数组，大小为 D+1，初始化为 0

过程:
  for i 从 1 到 n:
    for j 从 D 到 t(i):
      dp[j] = max(dp[j], dp[j - t(i)] + v(i))

返回 dp[D]

// 三维的0-1背包问题
// dp[w][v]=max(dp[w][v],dp[w−wi][v−ci]+vi)

输入: 物品数组 items，每个物品有重量 w_i、体积 c_i 和价值 v_i，以及最大重量 W 和最大体积 V
输出: 最大总价值

定义:
  dp = 二维数组，大小为 W+1 x V+1，初始化为 0

过程:
  for i 从 1 到 n:
    for j 从 W 到 w_i:
      for k 从 V 到 c_i:
        dp[j][k] = max(dp[j][k], dp[j - w_i][k - c_i] + v_i)

返回 dp[W][V]

输入: 下载请求带宽数组 a[n] 和最大带宽 K
输出: 子集 S 使得带宽利用最大

定义:
  dp = 一维数组，大小为 K+1，初始化为 0

过程:
  for i 从 1 到 n:
    for j 从 K 到 a[i]:
      dp[j] = max(dp[j], dp[j - a[i]] + a[i])

返回 K - dp[K]

输入: 数字三角形 triangle[n][n]
输出: 最大路径和

定义:
  dp = 数组，大小为 n，初始化为最后一行的值

过程:
  for i 从 n-2 到 0:
    for j 从 0 到 i:
      dp[j] = triangle[i][j] + max(dp[j], dp[j + 1])

返回 dp[0]