1.4 算法和算法分析

• 算法定义

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

• 算法描述

  • 自然语言：英文、中文。

    例如：求一元二次方程的根：
    1、输入方程的系数a、b、c
    2、判断a是否等于零，如果等于零，则提示不是一元二次方程。不等于零，则执行第3步。
    3、计算
    4、判断d。如果d等于零，计算并输出两个相等的实根。如果d小于零，输出没有的实根。如果d大于零。输出两个不等实根。
    5、结束。

  • 传统的流程图、NS流程图。

  • 伪代码：类语言：类C语言

  • 程序代码：C语言程序，Java语言程序

• 算法与程序

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

• 算法特性：一个算法不许具备一下五个重要的特性。

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

• 算法设计要求

  • 正确性(Correctness)
  • 可读性(Readability)
  • 健壮性(Robustness)
  • 高效性 (Efficiency)