本文记录了书中讲述的几个关于算法分析的概念和自己的理解，以及常见的增长数量级，方便日后查阅。

概念

  • 成本模型：这个模型定义了我们所研究的算法中的基本操作。通过明确成本模型，使给定的实现所需的运行时间增长数量级和它背后算法的成本的增长数量级相同（换句话说，成本模型应该和内循环中的操作有关。）
  • 命题：表示在某个成本模型下算法的数学性质。
  • 内循环：执行最频繁的指令决定了程序执行的总时间，我们将这些指令成为程序的内循环。
  • 问题的规模：问题的规模可以是输入的大小或是某个命令行参数的值。

常见增长数量级及对应算法

按从快到慢列出

  • 常数级别～普通语句
  • 对数级别～二分查找
  • 线性级别～使用常数时间处理输入数据中的所有元素或是基于单个for循环的程序
  • 线性对数级别～归并排序、快排
  • 平方级别～一般都有两个嵌套的for循环，比如选择排序、插入排序
  • 立方级别～一般含有三个嵌套的for循环，比如ThreeSum
  • 指数级别

参考

  • 《算法》p108-p130