算法设计与分析

算法设计与分析核心要点其中包含了几大基本算法设计思想，可以让我们对算法有一个清晰地整体认识，有助于我们更好的理解算法以及应试。复习时间不够，看这一张图就行了。

算法设计与分析

• 动态规划
  • 最优化问题
    • 有n个输入，它的解由这n个输入的一个子集组成，这个子集必须满足某些事先给定的条件，这些条件称为约束条件，满足约束条件的解称为问题的可行解。满足约束条件的可行解可能不只一个，为了衡量这些可行解的优劣，事先给出一定的标准，这些标准通常以函数的形式给出，这些标准函数称为目标函数，使目标函数取得极值（极大或极小）的可行解称为最优解，这类问题就称为最优化问题。
  • 最优性原理
    • 对于一个具有n个输入的最优化问题，其求解过程往往可以划分为若干个阶段，每一阶段的决策仅依赖于前一阶段的状态，由决策所采取的动作使状态发生转移，成为下一阶段决策的依据。从而，一个决策序列在不断变化的状态中产生。这个决策序列产生的过程称为多阶段决策过程
  • 动态规划的基本思想
    • 适合采用动态规划法求解的问题，经分解得到的各个子问题往往不是相互独立的。与分治法不同。
    • 在求解过程中，将已解决的子问题的解进行保存，在需要时可以轻松找出。这样就避免了大量的无意义的重复计算，从而降低算法的时间复杂性。
    • 如何对已解决的子问题解的保存呢？通常采用表的形式，即在实际求解过程中，一旦某个子问题被计算过，不管该问题以后是否用得到，都将其计算结果填入该表，需要的时候就从表中找出该子问题的解，具体的动态规划算法多种多样，但它们具有相同的填表格式
  • 动态规划的解题步骤
    • 分析最优解的性质，刻画最优解的结构特征—考察是否适合采用动态规划法
    • 递归定义最优值（即建立递归式或动态规划方程）
    • 以自底向上的方式计算出最优值，并记录相关信息
    • 根据计算最优值时得到的信息，构造出最优解
  • 动态规划的基本要素
    • 最优子结构性质
      • 子问题重叠性质
        • 递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题出现多次，这种性质称为子问题的重叠性质
        • 在应用动态规划时，对于重复出现的子问题，只需在第一次遇到时就加以解决，并把已解决的各个子问题的解储存在表中，便于以后遇到时直接引用，从而不必重新求解，可大大提高解题的效率
        • 自底向上的求解方式
  • 分析最优解的结构
    • 特征：计算A[i:j]的最优次序所包含的计算矩阵子链 A[i:k]和A[k+1:j]的次序也是最优的
    • 矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法求解的显著特征
• 分治法
  • 分治策略
    • 分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之
  • 设计思想
    • 将一个难以直接解决的大问题，划分成一些规模较小的子问题，以便各个击破，分而治之
    • 再将子问题的解合并为一个更大规模的问题的解，自底向上逐步求出原问题的解
  • 适用条件
    • 分治法所能解决的问题一般具有以下几个特征
    • 该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质
    • 利用该问题分解出的子问题的解可以合并为该问题的解
    • 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题
    • 这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划较好
  • 求解过程
    • 划分
      • 既然是分治，当然需要把规模为n的原问题划分为k个规模较小的子问题，并尽量使这k个子问题的规模大致相同
    • 求解子问题
      • 各子问题的解法与原问题的解法通常是相同的，可以用递归的方法求解各个子问题，有时递归处理也可以用循环来实现
    • 合并
      • 各个子问题的解合并起来，合并的代价因情况不同有很大差异，分治算法的有效性很大程度上依赖于合并的实现
  • 求解思路
    • 如何分，即如何合理地进行问题的分解？
      • 一分为二
    • 如何治，即如何进行问题的求解
      • 进行合并
    • 问题的关键——发现循环赛日程表制定过程中存在的规律性
  • 快速排序
    • 快速排序的分治策略是
      • 划分：
        • 选定一个记录作为轴值，以轴值为基准将整个序列划分为两个子序列r1 … ri-1和ri+1 … rn，前一个子序列中记录的值均小于或等于轴值，后一个子序列中记录的值均大于或等于轴值
      • 求解子问题
        • 分别对划分后的每一个子序列递归处理
      • 合并
        • 由于对子序列r1 … ri-1和ri+1 … rn的排序是就地进行的，所以合并不需要执行任何操作
    • 快速排序算法的分治策略体现
      • 分解
        • 在R[low:high]中选定一个元素作为基准元素(pivot)，以此基准元素为标准将待排序序列划分为两个子序列并使序列R[low:pivotpos-1]中所有元素的值均小于等于R[pivotpos]，序列R[pivotpos+1:high]中所有元素的值均大于等于R[pivotpos]
        • 求解子问题
          • 对子序列R[low:pivotpos-1]和R[pivotpos+1:high],分别通过递归调用快速排序算法来进行排序
        • 合并
          • 就地排序
• 贪心法
  • 设计思想
    • 贪心法在解决问题的策略上目光短浅，总是作出在当前看来最好的选择。而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。换言之，贪心法并不是从整体最优考虑，它所做出的选择只是在某种意义上的局部最优
  • 贪心法求解的问题的特征
  • 最优子结构性质
    • 当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质，也称此问题满足最优性原理。
  • 贪心选择性质
    • 所谓贪心选择性质是指问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来得到（仅在当前状态下做出最好选择）
  • 动态规划法通常以自底向上的方式求解各个子问题，而贪心法则通常以自顶向下的方式做出一系列的贪心选择
  • 求解过程
    • 候选集合C：为了构造问题的解决方案，有一个候选集合C作为问题的可能解，即问题的最终解均取自于候选集合C。例如，在付款问题中，各种面值的货币构成候选集合。
    • 解集合S：随着贪心选择的进行，解集合S不断扩展，直到构成一个满足问题的完整解。例如，在付款问题中，已付出的货币构成解集合。
    • 解决函数solution：检查解集合S是否构成问题的完整解。例如，在付款问题中，解决函数是已付出的货币金额恰好等于应付款
    • 选择函数select：即贪心策略，这是贪心法的关键，它指出哪个候选对象最有希望构成问题的解，选择函数通常和目标函数有关。例如，在付款问题中，贪心策略就是在候选集合中选择面值最大的货币
    • 可行函数feasible：检查解集合中加入一个候选对象是否可行，即解集合扩展后是否满足约束条件。例如，在付款问题中，可行函数是每一步选择的货币和已付出的货币相加不超过应付款
  • 算法正确性证明
  • 问题存在从贪心选择开始的最优解
    • 贪心选择性质
      • 采用归纳法
  • 一步一步的贪心选择能够得到问题的最优解
    • 最优子结构性质
      • 采用反证法
  • 核心构造思想
    • 权值大的叶子离根最近（频率高的字符编码短）
  • Prim和Kruskal算法的比较
    • 从算法的思想可以看出，如果图G中的边数较小时，可以采用Kruskal，因为Kruskal算法每次查找最短的边；边数较多可以用Prim算法，因为它是每次加一个顶点。可见，Kruskal适用于稀疏图，而Prim适用于稠密图
    • 从时间上讲，Prim算法的时间复杂度为O(n2)，Kruskal算法的时间复杂度为O(eloge)
    • 从空间上讲，显然在Prim算法中，只需要很小的空间就可以完成算法，因为每一次都是从个别点开始出发进行扫描的，而且每一次扫描也只扫描与当前顶点集对应的边。但在Kruskal算法中，因为时刻都得知道当前边集中权值最小的边在哪里，这就需要对所有的边进行排序，对于很大的图而言，Kruskal算法需要占用比Prim算法大得多的空间。
• 算法及基础知识
  • 算法
    • 指对特定的问题求解步骤的一种描述，是若干条指令的有穷序列
    • 特性
      • 输入
      • 输出
      • 确定性
      • 有限性
      • 可行性
  • 描述方式
    • 自然语言
      • 日常进行交流的语言
      • 优点
        • 简单
      • 通俗易缺点
        • 不够严谨
        • 烦琐
        • 不能被计算机直接执行
    • 图形
      • 工具
        • 流程图
        • N-S图
        • PAD图
      • 优点
        • 直观形象
        • 简洁明了
      • 缺点
        • 画起来麻烦
        • 不易修改
        • 不能被计算机直接执行
    • 程序设计语言
      • 能完整，准确和规则地表达人们的意图，并用以指挥和控制计算机工作的"符号系统"
    • 优点
      • 能被计算机直接执行
    • 缺点
      • 抽象性差
      • 不易理解
      • 有严格的格式要求
    • 伪代码
      • 介于自然语言和程序设计语言之间的一种用文字和符号结合的算法描述工具
  • 算法设计的一般步骤
    • 充分理解要解决的问题
    • 数学模型拟制
    • 算法详细设计
    • 算法描述
    • 算法思路的正确性验证
    • 算法分析
    • 算法的计算机实现和测试
    • 文档资料的编制
  • 算法分析（Algorithm Analysis）
    • 对算法所需要的两种计算机资源——时间和空间进行估算
      • 时间复杂性（Time Complexity）
      • 空间复杂性（Space Complexity）
    • 目的
      • 设计算法——设计出复杂性尽可能低的算法
      • 选择算法——在多种算法中选择其中复杂性最低者
    • 算法复杂性 = 算法运行时所需要的计算机资源的量
      • 时间复杂性
        • 影响时间复杂性的因素
          • 问题规模n、输入序列I、算法本身A
      • 空间复杂性
        • 影响空间复杂性的因素
          • 算法本身、输入输出数据、辅助变量
        • 算法复杂性的权衡
          • 时间复杂度和空间复杂度相互影响（时间换空间或空间换时间）
      • 三种情况下的复杂性（结合顺序查找操作）
        • 最好情况Tmin（N)
          • -1次
        • 最坏情况Tmax（N)
          • N次
        • 平均情况Tavg（N)
          • (N+1)/2
  • 非递归算法分析的一般步骤
    • 1. 决定用哪个（或哪些）参数作为算法问题规模的度量
      • 以从问题的描述中得到
    • 2. 找出算法中的基本语句
      • 通常是最内层循环的循环体。
    • 3. 检查基本语句的执行次数是否只依赖于问题规模
      • 如果基本语句的执行次数还依赖于其他一些特性，则需要分别研究最好情况、最坏情况和平均情况的效率
    • 4. 建立基本语句执行次数的求和表达式
      • 计算基本语句执行的次数，建立一个代表算法运行时间的求和表达式
    • 5. 用渐进符号表示这个求和表达式
      • 计算基本语句执行次数的数量级，用大O符号来描述算法增长率的上限
  • 递归
    • 子程序（或函数）直接调用自己或通过一系列调用语句间接调用自已，称为递归
  • 递归算法
    • 直接或间接调用自身的算法称为递归算法
    • 采用递归算法来求解问题的一般步骤：
      • 分析问题，寻找递归关系
      • 找出停止条件
      • 构建函数体