算法分析与设计复习

18 Jun 2024 1685字 6分

目录

算法设计基础

  1. 算法是解决问题的方法，是指令的有限序列。
  2. 算法的五个特性：输入、输出、有穷性、确定性、可行性。
  3. 描述算法的四种方式：自然语言、流程图、程序设计语言、伪代码。其中，自然语言具有二义性，程序设计语言最不易理解。
  4. 五种算法问题类型：查找问题、排序问题、图问题、组合问题、几何问题。

算法分析基础

  1. 算法的时间复杂性分析是一种事前分析估算的方法，它是对算法所消耗资源的一种渐进分析方法。
  2. 为了客观地反映一个算法的运行时间，可以用算法中基本语句的执行次数来度量算法的工作量。
  3. 大$O$符号用来描述增长率的上限。
  4. 非递归算法分析的一般步骤：
    • 确定问题的输入规模；
    • 找出算法中的基本语句：算法中执行次数最多的语句；
    • 检查基本语句的执行次数是否只依赖于输入规模；
    • 建立基本语句执行次数的求和表达式；
    • 用渐进符号表示求和表达式。
  5. 主定理（递归算法时间复杂度）$page~22$

蛮力法

  1. 是最容易应用的方法。所依赖的基本技术是遍历。

分治法

  1. 分治法求解过程的三个阶段：划分、求解子问题、合并。
  2. 分治法的适用条件：子问题独立；运行效率最高的情况：平衡子问题。
  3. 大部分分治算法的时间复杂度取决于合并阶段（快排不需要合并，是特例）。
  4. 快排、归并的过程。

动态规划法

  1. 动态规划法适用于求解多阶段决策最优化问题。
  2. 多阶段决策过程满足最优性原理。
  3. 动态规划法求解问题的三个阶段：划分子问题、确定动态规划函数、填写表格。
  4. 最长递增子序列问题、最长公共子序列问题（长度矩阵$L$、状态矩阵$S$）。

贪心法

  1. 典型应用是求解最优化问题。并不总能获得整体最优解，但通常能获得近似最优解。
  2. Prim算法：选点加入；Kruskal算法：选边加入。

回溯法

  1. 适用于求解组合数较大的问题。适用范围：找到可行解。基本思路是dfs（蛮力） + 剪枝（提高效率）。

分支限界法

  1. 适用于求解最优化问题。基本思路是bfs + 剪枝。
  2. 多段图最短路径问题，使用贪心法求上界。假设当前已经确定了前$i$段$(1 \leq i \leq k)$，限界函数（下界）：$lb = \Sigma_{j=1}^{i}c[r_j][r_{j+1}] + min_{<r_{i+1}, v_p> \in E}{c[r_{i+1}][v_p]} + \Sigma_{j=i+2}^k第j段的最短边$.
  3. 任务分配问题，使用贪心法求上界。假设已经对人员$1\sim i$分配任务，则限界函数（下界）：$lb = v + \Sigma_{k = i + 1}^n 第k行的最小值$。

计算复杂性理论

  1. $page 192$两张图。
  2. P类问题：如果对于某个判定问题$\Pi$，存在一个非负整数$k$，对于输入规模为$n$的实例，能够以$O(n^k)$的时间运行一个确定性算法，得到$yes$或$no$的答案，则该判定问题$\Pi$是一个P类问题。
  3. NP类问题：如果对于某个判定问题$\Pi$，存在一个非负整数$k$，对于输入规模为$n$的实例，能够以$O(n^k)$的时间运行一个非确定性算法，得到$yes$或$no$的答案，则该判定问题$\Pi$是一个NP类问题。

近似算法

  1. 适用于难解问题。
  2. 近似算法的基本思想：放弃求最优解，用近似最优解代替最优解，以换取算法设计上的简化和时间复杂性的降低。

概率算法

  1. 概率算法适用于：如果一个问题没有有效的确定性算法可以在一个合理的时间内给出解答，但是，该问题能接受小概率的错误。
  2. 三种概率算法：舍伍德型概率算法、拉斯维加斯型概率算法、蒙特卡罗型概率算法。
  3. 舍伍德型概率算法设法消除算法的不同输入实例对算法时间性能的影响。对于任何输入实例，舍伍德型概率算法能够以高概率与原有的确定性算法在平均情况下的时间复杂性相同。
  4. 拉斯维加斯型概率算法的随机性选择有可能导致算法找不到问题的解。即算法运行一次，或者得到一个正确的解，或者无解。
  5. 蒙特卡罗型概率算法用于求问题的准确解。蒙特卡罗型概率算法总是给出解，但是这个解偶尔可能是不正确的，且一般情况下无法判定解的正确性。求得正确解的概率依赖于算法的执行次数，算法的执行次数越多，得到正确解的概率就越高。