3.算法分析

算法(Algorithm)

算法是对特定问题求解步骤的一种描述。它是指令的有限序列,其中每一条指令表示一个或多个操作。

算法的特性

  1. 有穷性 算法须在有穷步之后结束,且每一步均在有穷时间内完成。
  2. 确定性 算法中的每一条指令含义必须是确切的。且,对于相同的输入只能得到相同的输出。
  3. 可行性 一个算法是可行的,它一定能够解决所描述的问题。
  4. 输入 一个算法有零个或多个输入。
  5. 输出 一个算法有一个或多个输出。这些输出同输入有某些特定的关系。

算法设计要求

  1. 正确性 设计的算法应当能够正确地解决待解问题。
  2. 可读性 设计的算法应当便于人们阅读与理解。
  3. 健壮性 设计的算法应当能够应对非法输入数据。
  4. 效率与低存储量需求 设计的算法执行所花的时间应尽量短,所耗费的存储空间应尽量少。

算法效率的度量

通过时间复杂度与空间复杂度描述。
1、时间复杂度 T(n) = O(f(n);n是问题规模。
2、空间复杂度 S(n) = O(g(n))