算法设计与分析

软考复习之算法设计与分析思维导图

算法设计与分析

• 基本概念
  • 算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作
  • 算法设计
    • 分治法
      • 将一个难以解决的大问题分解成一些规模较小的相同问题
      • 归并排序
    • 动态规划法
      • 适合用动态规划法求解的问题，经分解得到的子问题往往不是独立的
      • 适合情况
        • 最优子结构
        • 重叠子问题
    • 贪心法
      • 策略上根据信息做出选择，一旦选择不管结果如何都不会改变
      • 适合情况
        • 最优子结构
        • 贪心选择性质
    • 回溯法
      • 通用的解题法，系统地搜索一个问题的所有解或任一解。带有系统性和跳跃性的算法
    • 分支限界法
      • 类似回溯法是一种在问题的解空间树T上搜索问题解的算法
      • 种类
        • 队列式
        • 优先队列分支限界法
    • 概率算法
    • 近似算法
  • 算法分析
    • 算法分析是指对一个算法所需要的资源进行估算，所需要资源的越多，该算法的复杂度就越高
  • 算法的表示
    • 自然语言
    • 流程图
    • 程序设计语言
    • 伪代码
  • 算法分析基础
    • 时间复杂度
      • 由于时间复杂度与空间复杂度分别对算法占用的时间和空间资源进行分析，计算相似，且空间复杂度分析相对简单些
    • 渐进符号
      • O记号
        • 给出一个算法运行时间的渐进上界
      • Ώ
        • 用该记号给出一个算法运行时间的渐进下界
      • Θ
        • 用该记号给出一个算法运行时间的渐进上界和渐进下界，即渐进紧致界
    • 递归式
      • 非递归算法
        • 展开法
        • 代换法
        • 递归树算法