【1.3】算法的特性及分类

问题 —— 算法 —— 程序

一、基本概念

目标:问题求解

• 问题(problem)一个函数
• 从输入到输出的一种映射
• 算法(algorithm)一种方法
• 对特定问题求解过程的描述，是指令的有限序列
• 程序(program)
• 是算法在计算机程序设计语言中的实现

算法的特性

• 通用性
• 对参数化输入进行问题求解
• 保证计算结果的正确性
• 有效性
• 算法是有限条指令组成的指令序列
• 即由一系列具体步骤组成
• 确定性
• 算法描述中的下一步应执行的步骤必须明确
• 有穷性
• 算法的执行必须在有限步内结束
• 换句话说，算法不能含有死循环

皇后问题(四皇后)

二、基本算法分类

• 穷举法
• 顺序找K值
• 回溯、搜索
• 八皇后、树和图遍历
• 递归分治
• 二分找 K 值、快速排序、归并排序
• 贪心法
• Huffman 编码树、最短路 Dijkstra 算法、最小生成树 Prim 算法
• 动态规划
• 最短路 Floyd 算法

二分法找 k 值

于已排序顺序线性表

• 数组中间位置的元素值 kmid
• 如果 kmid = k，那么检索工作就完成了
• 当 kmid > k 时，检索继续在前半部分进行
• 相反地，若 kmid < k，就可以忽略 mid 以前的 那部分，检索继续在后半部分进行
• 快速
• kmid = k 结束
• Kmid ≠ k 起码缩小了一半的检索范围

思考:算法的时空限制

设计一个算法，将数组 A(0..n-1) 中的元素循环右移 k 位，假 设原数组序列为 a0, a1, …, an-2,an-1;移动后的序列为 an-k, an-k+1, …, a0, a1, …, an-k-1。要求只用一个元素大小的附加存 储，元素移动或交换次数与 n 线性相关。例如，n=10, k=3

参考资料

北京大学 《数据结构与算法》 张铭、赵海燕、宋国杰、黄骏、邹磊、陈斌、王腾蛟