任何算法的效率都是由算法的时间复杂度和空间复杂度决定的。
1、时间复杂度
时间复杂度是指算法完成其执行所花费的时间。相对于输入的大小,它可以用不同的时间复杂度类型表示:
BigO表示法(O):表示算法运行时间的上限,代表算法的最坏情况复杂度。如下图:
Omega表示法(Ω):表示算法运行时间的下限,代表算法的最佳情况复杂度。如下图:
Theta表示法(Θ):从上到下包围了函数。由于它代表了算法运行时间的上限和下限,因此用于分析算法的平均情况复杂度。如下图:
2、空间复杂度
空间复杂度是指算法完整执行所使用的内存总量。它包括辅助存储器和输入。
辅助存储器是算法在输入数据之外占用的额外空间。通常,辅助存储器被考虑用于计算算法的空间复杂度。