一、时间复杂度
当计算时间复杂度时,通常需要考虑算法中的循环次数、递归深度等因素。以下是一些常见时间复杂度的示例:
-
O(1):常数时间复杂度,表示算法的执行时间是固定的,与输入规模无关,比如直接访问数组中的某个元素。
-
O(log n):对数时间复杂度,通常出现在二分查找等算法中,每次迭代减少一半的数据规模。
-
O(n):线性时间复杂度,算法的执行时间与输入规模成正比,比如遍历数组中的所有元素。
-
O(n log n):线性对数时间复杂度,通常出现在快速排序、归并排序等分治算法中。
-
O(n^2):平方时间复杂度,通常出现在嵌套循环中,比如冒泡排序、选择排序等。
-
O(2^n):指数时间复杂度,通常出现在递归算法中,每次递归调用会产生指数级增长。
-
O(n!):阶乘时间复杂度,通常出现在全排列等需要枚举所有可能情况的算法中。
二、空间复杂度
计算算法的空间复杂度通常需要考虑算法在执行过程中所使用的额外空间大小,不包括输入数据占用的空间。以下是一些常见的空间复杂度示例: