算法设计

对迭代法、蛮力法、递归法进行总结，内容丰富，要点梳理，结构清晰，体系完整！非常值得学习！赶紧收藏一起学习吧！

算法设计

• 算法设计步骤
  • 算法设计七部曲：问题定义-问题分析-数学模型-计算模型-算法设计-算法分析-算法优化
  • 重复操作是复杂算法的重要特征，解决办法：循环结构，递归结构
• 迭代算法
  • 定义：用变量的旧值通过循环推演机制不断递推出该变量的新值的过程，直到某种条件得到满足为止。
  • 特点：用循环结构实现，循环代码中参与运算的变量同时是保存结果的变量
  • 算法分析
    • 算法正确——算法能实现解决问题的目标
    • 算法可终止——当输入确定的n值后，循环的次数是有限的，其他语句各执行一次，语句个数有限，算法执行有限次后必然终止。
    • 算法时间复杂度是O（n）
  • 迭代算法策略是利用待解决的问题所包含的子问题之间的某种递推关系求解问题的解的一种方法
    • 顺序递推法
      • 顺序递推法是利用问题本身所具有的一种递推关系求问题解的一种方法
        • 能采用顺序递推法构造算法的问题具有重要的递推性质
      • 兔子繁殖算法
    • 倒序递推法
      • 倒序递归法是第某些特殊问题所采用的违反通常习惯的，从后向前推解问题的方法。
      • 猴子吃桃问题
• 蛮力法
  • 定义：把问题的所有情况或过程交给计算机去一一尝试，从中找出问题的解。“力”指计算机的能力，而不是人的智力
  • 策略思想：采用某种方式将待解决问题的所有可能解一一列举出来，在列举过程中，逐一尝试或检查，从而找出满足条件的解
  • 典例：顺序查找，选择排序，冒泡排序，插入排序，矩阵乘法，字符串匹配等
  • 优点
    • 唯一几乎什么问题都能解决的一般性方法 对一些重要问题，可以产生一些合理的算法 可以解决一些小规模的问题实例 可以作为准绳，来衡量解决同样问题的高效算法（小规模）
  • 缺点
    • 当问题情况数目太多时，太费时间
  • 改进策略
    • 忽略一些明显不太可能的情况，以减少列举的可能解数目
  • 方法
    • 找出枚举范围：分析问题各种情况
    • 找出约束条件：分析问题的解需要满足的条件，并用逻辑表达式表示
  • 典例
    • 百鸡百钱问题提，狱吏问题，
• 递归算法
  • 定义：一个函数或过程在其定义或说明中又直接或间接调用自身的方法
  • 特征：把一个复杂的大问题层层转化为一个与原问题相似的较小问题，再逐步求解小问题，然后返回来求大问题的解
  • 优点：（1）算法简洁；（2）易分析
  • 缺点：执行效率低（时间多、占用贮存空间多）
  • 算法设计步骤
    • （1）构造递归关系：逐步使问题变小的规律（数学公式）； （2）找出递归停止条件：最小问题的解 （3）设计计算模型：根据（1）设计计算模型
  • 典例：汉诺塔问题
• 迭代和递归的比较
  • 递归是实现“重复操作”的一种机制，通过把大问题化小，小问题化到能解问题为止，再由小到大把问题的解“累积”起来，从而得到最大问题（原问题）的解，需要用到数据结构中的栈来暂时存储中间结果。
  • 重要结论
    • 每个迭代算法原则上总可以转换成与其功能等价的递归算法；反之不然
    • 注意：有些递归程序转化为非递归程序需要栈辅助，有些则不需要栈辅助