算法分析 | 大O分析

大 O 表示法用于衡量算法的复杂性。

常见的时间复杂度包括 O(1)、O(N)、O(N^2) 等。

算法的时间复杂度可分为对数算法、线性算法、超线性算法、多项式算法、指数算法和阶乘算法。

内存足迹分析是性能分析的重要指标，取决于程序实现和输入大小。

时间效率和空间效率通常是权衡的关系。

找到时间复杂度低且内存占用少的算法对性能有重要影响。

恒定时间函数为 O(1)，线性时间函数为 O(N)，二次时间函数为 O(N^2)。

Big-O 符号分析的一般步骤包括弄清输入、用 n 表示最大操作数、除去最高阶项和常数因子。

算法的运行时间复杂度从优到劣可分为对数算法、线性算法、超线性算法、多项式算法、指数算法和阶乘算法。

运行时间增长最快的算法是阶乘算法 O(n!)，即使在 n 值较小的情况下也很快变得不可用。

内存足迹分析的算法示例包括理想算法 O(1)、对数算法 O(log n)、线性算法 O(n) 等。

时空权衡通常需要在最佳内存使用和运行时性能之间进行权衡。

找到一种运行时间较短且对内存空间要求较低的算法可以显著提高算法性能。