算法复习

Previous Next

算法概念复习

算法概念

  • 图灵机
  • 有限状态控制器+无限延长工作带
  • 控制器 = 有限状态、一个读写头
  • 工作带 = 每个单元可放一个符号

  • 工作过程

    • 输入：工作带放一个输入符号
    • 转换：读写头扫描它并决定下一步动作，改变状态
    • 终止：重复此过程，直到终止

  • 渐进分析

  • 概念：忽略具体机器、编程语言和编译器的影响，只关注在输入规模增大时，算法运行时间的增长趋势的分析方法。

  • 大$O$符号：若存在两个正的常数c和n0，对于任意n>=n0，都有T(n)<=c*f(n)，则称T(n)=O(f(n))。该符号用于描述增长率的上限。
  • 大$\Omega$符号：若存在两个正的常数c和n0，对于任意n>=n0，都有T(n)>=c*g(n)，则称T(n)=Ω(g(n))。该符号用于描述增长率的下限。
  • 空间复杂度

  • 时间复杂度

    • 扩展递归技术：用于求解递推关系式。扩展就是根据递推式替换等式右边项，依此下去，会得到一个求和表达式，求和得到问题的解。
    • 主定理：略

  • 原地工作：如果算法需要的辅助空间相对于问题的输入规模来说是一个常数，我们称该算法是原地工作。

  • 算法

  • 概念：指令的有限序列

  • 算法的基本特点：输入，输出，有穷性，确定性，可行性（入出可定穷）
  • 好算法的特点：正确性，健壮性，可理解性，抽象性，高效性（正理抽高健）
  • 描述算法的方法：自然语言、流程图、程序设计语言、伪代码（伪语自流）
  • 研究的核心问题：速度、时间
  • 设计一般过程：分析问题（形成基本思路），存储到内存（将思路形成算法），将算法步骤转化为某种程序设计语言的语句。（形成语句）

  • 最优算法：若可证明时间下界Ω(𝑔(𝑛))存在，则以时间Ω(𝑔(𝑛))来求解该问题的任何算法

  • 论题与问题

  • Turing问题：一个问题是实际可计算的，当且仅当其在图灵机上经过有限步骤得到正确的结果。

  • Cook论题：一个问题是实际可计算的，当且仅当其在图灵机上经过多项式步骤得到正确的结果。

  • 选择问题：寻找T的第k小的元素的问题

  • 中值问题：找到T的中位数，当数据集大小为奇数时为中间值，为偶数时为中间两个数的平均值

image-20250107125241634

  • P问题、NP问题

    • 答题模板：对于某个判定问题，存在一个非负整数k，对于输入规模为n的样例，能以多项式时间运行一个[确定性/非确定性]算法，得到yes或no的结果。

  • NP-Hard问题

    • 规约：简单问题->复杂问题

    • 若所有NP问题都能规约到它，则它属于NPH问题（NP->NPH）

  • NPC问题：既属于NP问题，又属于NPH问题

  • 常见算法的时间复杂度

  • 顺序搜索：n

  • 二分搜索：最好1，最坏logn

  • 01背包（回溯法）：2^n
  • 01背包（dp）：C*n
  • 可拆分背包（贪心）：n
  • 快速排序：nlogn
  • 插入排序：n^2

算法基础

基础

  • 贪心选择性质：指的是一个问题的全局最优解可以通过一系列局部最优解（贪心选择）来得到。

  • 暴力

  • 贪心
分治
  • 平衡子问题：在用分治法设计算法时，最好使各个子问题的规模大致接近，这时算法的性能通常较好。
  • 分治法
  • 概念：将难解决的大问题，划分成一系列规模较小的子问题，分别==求解子问题==，最后在==合并子问题的解==得到原问题的解。求解过程包括：分、治、合
  • 减治法
  • 二分搜索
搜索
  • 解空间树：
  • 概念：解空间树是一棵树状结构。根节点=搜索的初始状态，第2层的结点=解向量的第一个分量做出选择后到达的状态，第1层到第2层的边上标出对第一个分量选择的结果， 以此类推，从而构造出解空间的树状结构。
  • 回溯法（基于DFS）
  • 分支限界法（基于BFS）
  • 概念：
    1. 确定限界函数，并根据其确定目标函数的界[down,up]。
    2. 按照BFS搜索解空间树。
    3. 对每一个分支节点都扩展其子节点，并估算子节点的目标函数的值。
    4. 若子节点的值超出目标函数的界，则丢弃；否则加入到结点表。
    5. 依次从结点表中取出“使目标函数取得极值”的结点，成为当前节点。
    6. 重复上述过程。
  • 关键问题：如何确定合适的限界函数（用于剪枝）；如何组织待处理结点表（优化查找）；如何确定最优解的各个分量（保存搜索路径）
  • 启发式搜索
动态规划
  • 记忆化搜索
  • 动态规划
概率
  • 蒙特卡洛
  • 舍伍德
  • 概念：（1）在确定性算法的某些步骤中引入随机因素，将确定性算法改造成舍伍德型概率算法；（2）借助于随机预处理技术，对输入实例随机排列（洗牌)，然后再执行确定性算法。
  • 拉斯维加斯
  • 概念：对相同的输入反复运行算法，直到有解。其正确解的概率与运行次数成正比。
近似
  • 近似比：若一个最优化问题的最优值为c*，求解该问题的一个近似算法得到的最优值为c，则该算法的近似比为c/c*或c*/c(取其中的大值)，用以衡量两者的接近程度。
群智能

  • 概念：群智能算法模拟昆虫、鸟等群体动物的社会行为机制，通过定义个体行为和群体行为，使群体具有种群多样化与行为指向性， 利用群体优势，为复杂问题提供解决方案。

  • 遗传

  • 概念：是一种模拟生物进化过程的计算模型，从任意初始种群出发，通过选择、交叉和变异等遗传操作，使种群一代一代进化到搜索空间中越来越好的区域，直至达到最优解。
  • 适应度：用来评价种群中每个个体在优化过程中可能达到最优解的程度。
  • 蚁群
  • 粒子群

算法专题

贪心和暴力
  • 串匹配问题
  • 概念：给定两个串S和T，在主串S中查找子串T。
  • 解法：暴力（BF）
动态规划
  • 背包问题
  • 子序列问题
搜索
  • N皇后问题
  • 冲突判断：假设定义解向量[x1,...,xn]表示皇后所在列。行不存在冲突，列、对角线冲突自己算
多方法的问题
  • TSP问题
  • 暴力法
  • 贪心法
  • 回溯法

  • 分支限界法

  • 多阶段决策问题

  • 概念：将问题的求解过程划分为若干阶段，每一阶段的决策仅依赖于前一阶段的状态（依赖前一阶段），由决策所采取的动作使状态发生转移（状态转移），成为下一阶段决策的依据。

    • 解决思路：把每一阶段当作子问题，然后按照由小问题到大问题，依次求解所有子问题，最终得到原问题的解。

  • 暴力法

  • 贪心法
  • 回溯法
  • 分支限界法
图论 LinearAlgebra