算法分析

Algorithm

算法: 分治法

递归法

贪心算法

动态规划法

回溯法
目的: . 分析某个算法的设计、时间复杂度、空间复杂度

分治法

特点: . 问题可以划分为n个小问题; . 小问题彼此独立; . 与原问题形式相同; . 采用递归分而治之：解决子问题从而解决主问题
步骤: . 分解→解决→合并
常见算法: 快速排序

二分查找

合并排序

递归法

特点: . 深度优先查找; . 走不通|找不到就回退；逐步试探; . 二叉树的遍历

贪心算法

特点: . always makes the choice that seems to be the best at that moment.; . not an algorithm, it is a technique; . Minimum Spanning Tree、Huffman codes ( data-compression codes ); . 局部最优; . 如果贪心不成立，则使用动态规划

回溯法

特点: . 递归的特例; . 选优搜索; . 要求设计者找出所有可能的搜索方法。是一种穷举搜索法; . 走不通|找不到就回退；逐步试探; . 试探的过程中，产生解空间 - 已经获取了部分答案
经典算法: 迷宫

N皇后

图的深度遍历DFS

正则表达式匹配