算法

[!NOTE] 算法
对特定问题求解方法和步骤的一种描述，它是指令的有限序列。每个指令表示一个或多个操作。简而言之，算法就是解决问题的方法和步骤。

• 算法的描述
  • 自然语言：英语、中文
  • 流程图： 传统流程图、NS流程图
  • 伪代码：类语言： “类C语言”
  • 程序代码： C语言程序、JAVA语言程序 ……

算法与程序

• 算法与程序
  • 算法是解决问题的一种方法或一个过程，考虑如何将输入转换成输出，一个问题可以有多种算法。
  • 程序是用某种程序设计语言对算法的具体实现。 程序 = 数据结构 + 算法
    • 数据结构通过算法实现操作
    • 算法根据数据结构设计程序

算法特性

• 算法特性： 一个算法必须具备以下五个重要特性
  • 有穷性 一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。
  • 确定性 算法中的每一条指令必须有确切的含义，没有二义性，在任何条件下，只有唯一的一条执行路径，即对于相同的输入只能得到相同的输出。
  • 可行性 算法是可执行的，算法描述的操作可以通过已经实现的基本操作执行有限次来实现。
  • 输入 一个算法有零个或多个输入。
  • 输出 一个算法有一个或多个输出。

算法设计的要求

• 正确性(Correctness)
  1. 程序中不含语法错误；
  2. 程序对于几组输入数据能够得出满足要求的结果；
  3. 程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足要求的结果
  4. 程序对于一切合法的输入数据都能得出满足要求的结果。
     通常以第三层意义上的正确性作为衡量一个算法是否合格的标准
• 可读性(Readability)
  1. 算法主要是为了人的阅读和交流，其次才是为计算机执行，因此算法应该易于人的理解；
  2. 另一方面，晦涩难读的算法易于隐藏较多错误而难以调试。
• 健壮性(Robustness)
  1. 指出输入非法数据时，算法恰当的做出反应或进行相应处理，而不是产生莫名其妙的输出结果。
  2. 处理出错的方法，不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理
     健壮性又称鲁棒性
• 高效性(Efficiency)
  1. 要求花费尽量少的时间和尽量低的存储要求