自学内容网 自学内容网

[数据结构与算法·C++] 笔记 1.3 算法特性

1.3 算法特性

目标: 问题求解

  • 问题(problem)一个函数

    • 从输入到输出的一种映射
  • 算法(algorithm)一种方法

    • 对特定问题求解过程的描述,是指令的有限序列
  • 程序(program)

    • 是算法在计算机程序设计语言中的实现

算法的特性

  • 通用性

    • 对参数化输入进行问题求解
    • 保证计算结果的正确性
  • 有效性

    • 算法是有限条指令组成的指令序列
    • 即由一系列具体步骤组成
  • 确定性

    • 算法描述中的下一步应执行的步骤必须明确
  • 有穷性

    • 算法的执行必须在有限步内结束
    • 换句话说,算法不能含有死循环

基本算法分类

  • 穷举法

    • 顺序找 K 值
  • 回溯(能进则进,不进则换)、搜索

    • 八皇后、树和图遍历

  • 递归分治

最优子结构
子结构不重复

  • 二分找 K 值、快速排序、归并排序

  • 贪心法

最优子结构
贪心性质

  • Huffman 编码树、最短路 Dijkstra 算法、最小生成树 Prim 算法


  • 动态规划

最优子结构
子结构重复
后无后效性

  • 最短路 Floyd 算法

原文地址:https://blog.csdn.net/qq_42995393/article/details/142419143

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!