1.2.2 算法效率的度量

教材导航 · 第1章

原书定位

印刷页P5起,对应PDF第17页。下文为目视整理的知识提要;完整内容见原书对照。

基本操作的执行次数刻画运行时间。顺序执行的复杂度取较大的数量级;嵌套循环应按实际次数求和,只有循环次数相互独立时才能直接相乘。

O(1)<O(log⁡n)<O(n)<O(nlog⁡n)<O(n2)<O(n3)<O(2n)<O(n!)O(1)<O(\log n)<O(n)<O(n\log n)<O(n^2)<O(n^3)<O(2^n)<O(n!)
  • O(f(n))O(f(n)) 给出渐近上界;严格的同阶界用 Θ(f(n))\Theta(f(n))。教材习题常以大 O 书写主导数量级。
  • 平均复杂度是给定输入分布下的期望,不必一概假定所有输入等概率;最坏复杂度给出最差情况下的保证。
  • 空间复杂度通常计额外辅助空间,递归还要计算调用栈。原地工作指辅助空间为 O(1)O(1)。
  • 倍增或折半循环常为对数级;三角形嵌套通常用等差求和;递归用递推式或递归树分析。

对应练习

1.2 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P5,PDF第17页

原书对照,原书P6,PDF第18页