算法分析

算法定义：
是指在解决问题时，按照某种机械步骤一定可以得到问题结果的处理过程。（解决问题的方法和步骤）

算法三要素：
操作、控制结构、数据结构

常见控制结构：
顺序、循环、选择

算法基本特征：
有穷性、确定性、可行性、0个或多个输入、一个或多个输出

算法的基本性质：
目的性、分步性、有序性、有限性、操作性

算法质量指标：
正确性、可读性、稳健性、高效率和低存储量

算法评价标准：
时间耗费、空间耗费、可读性

常见时间复杂度排序：
O(1) < O(lgn) < O(n) < O(nlgn) < O(n²) < O(n³) < O(2ⁿ) < O(n!) < O(nⁿ)

时间复杂度
算法的时间复杂度是一个函数，它 定性 描述了该算法的运行时间。

辗转相除法

gcd(x, y):
    if (y == 0)  
        return x
    else  
        return gcd(y, x % y)

时间复杂度：O(lgn)

汉诺塔问题：
时间的递推公式：T（n）=2T（n-1)+1，时间复杂度为 O(2ⁿ)

• 每个迭代算法原则上总可以转换为与之等价的递归算法
• 并不是每个递归算法都可以转化为与之等价的循环结构算法
• 递归是一种比循环更强、更好用的实现“重复操作”的机制。

递归设计要点：

• 分析问题，找递归关系
• 设置边界、控制

迭代算法的步骤：

• 确定迭代模型
• 根据迭代模型，建立迭代关系式
• 对迭代过程进行控制，确定什么时候结束迭代

枚举法（穷举法）步骤：
根据问题中的条件将可能的情况一一列举，逐一尝试找出满足问题的解。从两个方面进行：1、找出枚举范围。2、找出约束条件

分治算法的步骤：
是将整个问题分解为若干个小问题后分而治之。分治法在每一层递归上都有3个步骤：

• 分解：分解为若干个相互独立、与原问题形式相同的子问题
• 解决：直到分解为容易解决的小问题，就解决之
• 合并：将已求解的各个子问题的解合并为原问题的解。

贪婪算法：（某状态以后的过程不影响以前状态，无后效性）

• 从问题的某一个初始解触发逐步逼近给定目标，每一步都作一个不可回溯的决策，尽可能求得最好的解
• 达到某一步不需要再继续前进时，算法停止

它可用于求问题最优解，但前提是“局部最优策略能产生全局最优解”。适用范围比较小，如果应用不当，则不能保证求得全局最优解。

动态规划：（多阶段最优化决策问题的过程）

• 找出最优解性质，并刻画结构特征
• 递归的定义最优值
• 自底向上的方式计算出最优值
• 根据计算最优值的信息，构造最优解

子集树，遍历耗时 O(2ⁿ)

排列树，遍历耗时 O(n !)

迭代算法：

• 递推法（正推）
• 倒推法（倒推）

全面逐一尝试比较的算法有：

• 枚举法
• 蛮力法
• 递归回溯法

隐式图搜索策略：

• 分支界限法（背包问题）
• 回溯法（8皇后）

图的搜索算法：

• 显式图：
  • 穷举搜索：广度优先、深度优先
• 隐式图：
  • 穷举搜索：回溯算法、分支算法
• 图的启发式算法：分支界限法

递归比循环：代码量小、占用空间大、适用范围广、执行时间要长