算法的基本概念

定义

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

程序可以理解为：数据结构 + 算法。数据结构负责把现实问题中的信息组织到计算机中，算法负责高效处理这些信息以解决问题。

算法必须具备的特性

  • 有穷性：算法必须在执行有穷步后结束，且每一步都在有穷时间内完成。算法必须有穷，程序可以长期运行。
  • 确定性：每条指令含义明确；相同输入只能得到相同输出。
  • 可行性：算法中的操作都能通过已经实现的基本运算执行有限次完成。
  • 输入：一个算法有零个或多个输入。
  • 输出：一个算法有一个或多个输出。

好算法追求的目标

  • 正确性：能正确解决问题。
  • 可读性：便于人理解、检查和维护。
  • 健壮性：遇到非法输入时能适当处理，而不是产生无意义结果。
  • 高效率与低存储量需求：时间复杂度和空间复杂度尽量低。

描述方式

算法可以用自然语言、伪代码、程序代码、流程图等方式描述。关键不是形式，而是步骤必须无歧义，并能在有限步骤内完成。

关联

评价算法时，先确认它满足算法的基本特性，再看正确性、可读性、健壮性、时间效率和空间需求。