1. 时间复杂度(Time Complexity)
时间复杂度用于衡量算法执行所需的时间随输入规模(通常是输入的长度 n
)增长的速率。常见的时间复杂度表示方式如下:
- O(1): 常数时间,无论输入规模如何,执行时间都相同。
- O(log n): 对数时间,常见于二分查找等算法,执行时间随着输入规模的对数增长。
- O(n): 线性时间,算法执行时间与输入规模成正比,例如遍历数组。
- O(n log n): 线性对数时间,常见于高效排序算法,如归并排序和快速排序的平均情况。
- O(n^2): 二次时间,常见于嵌套循环算法,比如冒泡排序。
- O(2^n): 指数时间,常见于解决组合问题的递归算法,如递归解决汉诺塔问题。
- O(n!): 阶乘时间,常见于排列问题,比如生成全排列。
如何计算时间复杂度?
- 确定基本操作的次数:例如循环中的单步操作。
- 忽略低阶项和常数:时间复杂度只关注增长的趋势,因此高阶项是最重要的。例如,
O(3n^2 + 5n + 2)
简化为O(n^2)
。
示例:
def linear_search(arr, target):for i in range(len(arr)):if arr[i] == target:return ireturn -1
这个算法的时间复杂度是 O(n)
,因为在最坏情况下需要遍历整个数组。
2. 空间复杂度(Space Complexity)
空间复杂度用于衡量算法在运行过程中所需内存空间的增长情况,同样以输入规模 n
为变量。主要考虑以下两部分:
- 固定空间:不依赖输入规模的内存占用,例如常量变量的占用空间。
- 可变空间:与输入规模相关的内存占用,比如动态分配的数组、递归调用栈等。
常见的空间复杂度表示方式与时间复杂度类似:
- O(1): 常量空间,不随输入规模变化,例如算法只使用了固定数量的变量。
- O(n): 线性空间,空间需求随输入规模线性增长,例如存储一个大小为
n
的数组。 - O(n^2): 二次空间,例如使用二维数组的动态规划算法。
示例:
def recursive_factorial(n):if n == 1:return 1else:return n * recursive_factorial(n-1)
这个递归算法的空间复杂度是 O(n)
,因为递归调用栈的深度为 n
。
总结:
- 时间复杂度衡量算法的执行时间随输入规模变化的速率,主要用于评估算法的效率。
- 空间复杂度衡量算法所需的内存空间随输入规模的变化,主要用于评估内存使用情况。
- 理解时间复杂度和空间复杂度有助于选择更高效的算法,并在代码优化时做出合理的决策。
通过分析算法的复杂度,可以帮助你在开发中做出更有效的选择,从而提高程序的执行效率。