【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

参考资料

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

个人公众号,比较懒,很少更新,可以在上面提问题,如果回复不及时,可发邮件给我: tiehan@sina.cn

Sam avatar
About Sam
专注生物信息 专注转化医学