跳转至

小结

算法效率评估

  • 「时间效率」和「空间效率」是算法性能的两个重要的评价维度。
  • 我们可以通过「实际测试」来评估算法效率,但难以排除测试环境的干扰,并且非常耗费计算资源。
  • 「复杂度分析」克服了实际测试的弊端,分析结果适用于所有运行平台,并且可以体现不同数据大小下的算法效率。

时间复杂度

  • 「时间复杂度」统计算法运行时间随着数据量变大时的增长趋势,可以有效评估算法效率,但在某些情况下可能失效,比如在输入数据量较小或时间复杂度相同时,无法精确对比算法效率的优劣性。
  • 「最差时间复杂度」使用大 \(O\) 符号表示,即函数渐近上界,其反映当 \(n\) 趋于正无穷时,\(T(n)\) 处于何种增长级别。
  • 推算时间复杂度分为两步,首先统计计算操作数量,再判断渐近上界。
  • 常见时间复杂度从小到大排列有 \(O(1)\) , \(O(\log n)\) , \(O(n)\) , \(O(n \log n)\) , \(O(n^2)\) , \(O(2^n)\) , \(O(n!)\)
  • 某些算法的时间复杂度不是恒定的,而是与输入数据的分布有关。时间复杂度分为「最差时间复杂度」和「最佳时间复杂度」,后者几乎不用,因为输入数据需要满足苛刻的条件才能达到最佳情况。
  • 「平均时间复杂度」可以反映在随机数据输入下的算法效率,最贴合实际使用情况下的算法性能。计算平均时间复杂度需要统计输入数据的分布,以及综合后的数学期望。

空间复杂度

  • 与时间复杂度的定义类似,「空间复杂度」统计算法占用空间随着数据量变大时的增长趋势。

  • 算法运行中相关内存空间可分为输入空间、暂存空间、输出空间。通常情况下,空间复杂度不计入输入空间。暂存空间可分为指令空间、数据空间、栈帧空间,其中栈帧空间一般在递归函数中才会影响到空间复杂度。

  • 我们一般只关心「最差空间复杂度」,即统计算法在「最差输入数据」和「最差运行时间点」下的空间复杂度。
  • 常见空间复杂度从小到大排列有 \(O(1)\) , \(O(\log n)\) , \(O(n)\) , \(O(n^2)\) , \(O(2^n)\)