填空题

算法概述

算法的定义

• 不是问题的答案，而是解决问题的操作步骤

• 算法就是一组有穷的规则，它们规定了解决某一特定类型问题的一系列运算。

• 程序与某种语言有关，能直接在机器上运行。

• 算法与特定的语言无关，可以用任何语言实现，甚至可以用自然语言实现。

• 算法与程序的区别是算法应具备有穷性；实际应用中，常用数学分析和后验分析相结合的方式来分析算法的性能。

• 有穷性

• 确定性

• 可行性

• 输入

• 输出

• 自然语言

• 程序流程图

• 程序设计语言

• 伪代码：是介于自然语言和程序设计语言之间的方法，采用某一程序设计语言的基本语法，操作指令可以结合自然语言来设计。

• 查找

• 排序

• 图

• 组合

• 集合

• 正确性

• 健壮性

• 可读性

• 可扩展性

算法的复杂性

• 在进行问题的计算复杂性分析之前，首先必须建立求解问题所用的计算模型。3个基本计算模型是随机存储机（RAM）模型、随机存取存储程序机（RASP）模型和图灵机（TM）模型。

• 算法的复杂性是算法运行所需要的计算机资源的量的度量，是评价算法优劣的重要依据。

• 计算机的资源最重要的是时间和空间资源，因而算法的复杂性有时间复杂性和空间复杂性之分。

• 衡量一个算法好坏的标准是时间复杂度低。

• 通常将能用多项式时间求解的问题称为易解问题，将需要指数时间求解的问题称为难解问题。

• 能在多项式时间内运行确定性算法求解判定问题称为P类问题；能在多项式时间内运行非确定性算法求解的判定问题称为NP类问题。
• 如果一个问题是 NP 问题，并且所有的 NP 问题都可以在多项式时间内归约到它，则该问题属于 NPC 问题。

• 计数法

• 计时法

具体算法

蛮力法

• 枚举范围：确定穷举的范围

• 约束条件：保证处理过的元素不再被处理

分治法与减治法

• 递归函数

• 递归调用

• 递归的2个基本要素

• 分治法：归并排序

• 减治法：堆排序

• 讲一个规模为n的问题分解为k个规模较小的子问题，这些子问题相互独立且与原问题相同，对着k个子问题分别求解，将求出的小规模分体的解合并为一个更大规模的问题的解，自底向上逐步求出原问题的解。

• 把一个大问题划分为若干个子问题，但是只需要求解其中的一个子问题，也无需对子问题的解进行合并。

• 原问题的解与子问题的解之间存在某种确定的关系。
• 原问题的解只存在与其中一个较小规模的子问题中。
• 原问题的解与其中一个较小规模的解之间存在某种确定的对应关系。

动态规划法与贪心法

• 动态规划法用于求解多阶段决策最优化问题。

• 最优子结构性质——某一问题可用动态规划算法求解的显著特征。

• 重叠子问题性质

• 最优子结构性质：一个问题的最优解包含其子问题的最优解，也称此问题满足最优性原理。

• 贪心选择性质：问题的整体最优解可以通过一系列局部最优解的选择，即贪心选择来得到。

• 划分子问题：将原问题的求解过程划分为若干个阶段，每个阶段对应一个子问题，并且子问题之间具有重叠关系。

• 动态规划函数：根据子问题之间的重叠关系找到子问题满足的递推关系式，这是动态规划法的关键。

• 填写表格：根据动态规划函数设计表格，以自底向上的方式计算各个子问题的最优值并填表，实现动态规划过程。

• 把一个复杂问题分解为一系列较为简单的局部最优选择，每一步选择都是对当前解的一个扩展，直至获得问题的完整解。

• 贪心算法总是做出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优解。

回溯法与分支限界法

• 回溯法采用深度优先的策略搜索解空间树

• 分支限界法采用广度优先的策略搜索解空间树

• 回溯法可以看作是蛮力法的一种改进策略。

• 回溯法从根节点出发，按照深度优先策略遍历问题的解空间树，搜索满足约束条件的解。对于解空间树的某个节结点如果该结点满足问题的约束条件，则进入该子树继续进行搜索，否则跳过该结点为根的子树，也就是剪枝。

• 对于最大化问题
• 上界：根据界限函数确定目标函数的上界。
• 下界：用某种启发方法得到目标函数的下届。

• 确定合适的限界函数——能在搜索的早期对超出目标函数界的节点进行丢弃。

• open表的存储结构

• 确定最优解的各个分量

具体问题

排序算法的时间复杂度

流水作业调度问题

0/1背包问题

n皇后问题

数塔问题

Dijkstra算法

最长公共子序列

Kruskal算法

归并排序

循环赛

哈夫曼算法

TSP问题