时间复杂度与空间复杂度

1. 时间复杂度（Time Complexity）

时间复杂度用于衡量算法执行所需的时间随输入规模（通常是输入的长度 n）增长的速率。常见的时间复杂度表示方式如下：

• O(1): 常数时间，无论输入规模如何，执行时间都相同。
• O(log n): 对数时间，常见于二分查找等算法，执行时间随着输入规模的对数增长。
• O(n): 线性时间，算法执行时间与输入规模成正比，例如遍历数组。
• O(n log n): 线性对数时间，常见于高效排序算法，如归并排序和快速排序的平均情况。
• O(n^2): 二次时间，常见于嵌套循环算法，比如冒泡排序。
• O(2^n): 指数时间，常见于解决组合问题的递归算法，如递归解决汉诺塔问题。
• O(n!): 阶乘时间，常见于排列问题，比如生成全排列。

如何计算时间复杂度？

1. 确定基本操作的次数：例如循环中的单步操作。
2. 忽略低阶项和常数：时间复杂度只关注增长的趋势，因此高阶项是最重要的。例如，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。

总结：

• 时间复杂度衡量算法的执行时间随输入规模变化的速率，主要用于评估算法的效率。
• 空间复杂度衡量算法所需的内存空间随输入规模的变化，主要用于评估内存使用情况。
• 理解时间复杂度和空间复杂度有助于选择更高效的算法，并在代码优化时做出合理的决策。

通过分析算法的复杂度，可以帮助你在开发中做出更有效的选择，从而提高程序的执行效率。