大 O 表示法(Big O Notation)是一种用于描述算法的时间复杂度(时间性能)和空间复杂度(空间使用)的数学表示法。
它帮助我们衡量算法在输入规模增大时,时间和空间消耗的增长速度。
大 O 表示法通常用于分析算法的性能,以便在不同算法之间做出更好的选择。
-
O(1):常数时间复杂度。无论输入规模如何增加,算法的执行时间都保持不变。例如,访问数组元素。
-
O(log n):对数时间复杂度。算法的执行时间随着输入规模的增加而增加,但增长速度较慢。例如,二分查找算法。
-
O(n):线性时间复杂度。算法的执行时间与输入规模成正比。例如,线性搜索。
-
O(n log n):线性对数时间复杂度。通常在使用分治法的排序算法(如快速排序、归并排序)中出现。
-
O(n^2):平方时间复杂度。算法的执行时间与输入规模的平方成正比。例如,嵌套循环的算法。
-
O(n^c):多项式时间复杂度,其中 c 是常数。常见的排序算法如冒泡排序,通常具有二次时间复杂度。
-
O(2^n):指数时间复杂度。算法的执行时间随着输入规模的增加呈指数级增长。通常出现在递归算法中。
还有其他更高阶的时间复杂度,如 O(n!) 和 O(n^n),但这些通常是非常低效的算法,只在小规模输入上才能使用。
大 O 表示法的目的是提供一种快速了解算法性能的方式,而不必关注具体的常数因子和低阶项。当比较不同算法时,我们更关心它们的增长率。
要注意,大 O 表示法描述的是算法的上界,即在最坏情况下的性能。