230. 算法设计与分析

发表于 更新于 分类于
基础内容

引论

Q. Suppose I need to solve an NP-complete problem. What should I do?A. Sacrifice one of three desired features.

  1. Solve arbitrary instances of the problem.
  2. Solve problem to optimality.
  3. Solve problem in polynomial time.

Q. Coping strategies.

  1. Design algorithms for special cases of the problem.
  2. Design approximation algorithms or heuristics.
  3. Design algorithms that may take exponential time.

算法复杂性分析

算法分析是对一个算法需要多少计算时间和存储空间作定量的分析。

输入规模度量

  • 算法的时间效率和空间效率都用输入规模的函数进行度量。
  • 对相同大小的输入实例具有相同的分析结果。
  • 对于所有的算法，对于规模更大的输入都需要运行更长的时间。
  • 经常使用一个输入规模n为参数的函数来研究算法的效率。

运行时间的度量单位

  • 用算法的基本操作（算法中最重要的操作）的执行次数来度量算法的时间效率。
  • 基本操作通常是算法最内层循环中最费时的操作。

算法运行时间的估计：

$$
T(n) ≈ copC(n)
$$

  • n 是该算法的输入规模
  • cop是特定计算机上一个算法基本操作的执行时间
  • C(n)是该算法需要执行的基本操作的次数