第2章 计算机基础知识

2.3 算法结构

一、递归技术

• 直接或间接的调用自身的算法被称为递归算法

• 递归：

  • 有一个明确的递归结束条件，递归出口

  • 递归调用受到条件控制，每次被调用，调用条件被修改。

  • 递归算法一般包含的三个基本部分：

    • 当前问题Q_n

    • 从较简单问题Q_{n-1}到Q_n的操作

    • 已解决的基本问题Q_0

二、分治法

• 将规模为n的问题分解为k个规模较小的子问题，而这些问题相互独立且可分别求解，再将k个子问题合并成原来的问题的解
• 分治法中，子问题通常与原问题相同，从而导致递归过程。

三、贪心算法

• 问题求解被划分为多步选择，每次都是允许的范围内找当前最好的选择，由每一步选择构成问题的最终解。

• 只能得到局部最优解，但不总能得到最优解

四、 回溯法

• 又称万能算法

• 求解过程相当于在所有可能解构成解空间树,搜索满足约束条件的解

五、动态规划法

• 用来求最优化问题，如TSP问题

• 化为多步策略，问题的最优解由子问题的最优解推导得到，则先求子问题最优解，再由子问题最优解构造原问题的最优解。

• 分为递归方式、非递归方式

六、算法分析

• 时间复杂度
• 空间复杂度