算法设计与分析复习资料.doc
版权申诉
127 浏览量
2022-05-06
22:13:23
上传
评论
收藏 331KB DOC 举报
一 名词翻译
Algorithm Design and Analysis 算法设计与分析
Algorithm Introduction 算法引论
Divide and conquer 分治法
Merge Sort 合并排序
Quick sort 快速排序
Linear Time Selection 线性时间选择
Dynamic programming 动态规划
Strassen 矩阵乘法
Matrix chain multiplication 矩阵连乘
Large integers multiply 大整数乘法
Longest common subsequence 最长公共子序列
Load problem 装载问题
Optimal loading 最优装载
Subset Tree 子集树
Permutation tree 排列树
Single-Source Shortest Paths 单源最短路径
Minimum spanning trees 最小生成树
Greedy Algorithms 贪心算法
Backtracking method 回溯法
Iterative backtracking 迭代回溯
Recursive backtracking 递归回溯
Branch and bound methods 分支界限法
Activity arrangement 活动安排
Solution space 解空间
注：使用分治思想的算法有：二分搜索技术 合并排序 快速排序
1 算法是指解决问题的方法或过程。
2 算法的四个特性：输入（有零个有多个）、输出（至少有一个）、确定性、有限性。
3 程序是算法用某种程序设计语言的具体实现。程序可以不满足有限性，如操作系统。
4 算法复杂性是算法运行所需要的计算机资源的量，需要时间资源的量称为时间复杂性，
需要的空间资源的量称为空间复杂性。
5 算法的复杂性分析对算法的设计或选用有重要的指导意义和实用价值（即为其目的）。
6 直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。
7 递归的优缺点：（优点）结构清晰，可读性强，而且容易用数学归纳法来证明算法的正
确性，因此它为设计算法、调试程序带来很大方便。 （缺点）递归算法的运行效率较
低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。
8 分治法的设计思想：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，
以便各个击破，分而治之。
9 分治法的步骤：（1）将一个规模为 n 的问题分解为 k 个规模较小的子问题，这些子问题
互相独立且与原问题相同。（2）递归地解这些子问题。（3）将子问题的解合并得到原
问题的解。
10 分治法的适用条件：（1）该问题的规模缩小到一定的程度就可以容易地解决；（2）该
问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；（3）利
用该问题分解出的子问题的解可以合并为该问题的解；（4）该问题所分解出的各个子
1
资源评论
