时间复杂度与空间复杂度

时间复杂度和空间复杂度用于评估算法效率。

时间复杂度描述算法完成所需的时间，常见类型包括常数时间O(1)、对数时间O(log n)、线性时间O(n)等。

常数时间O(1)：算法执行时间不随输入大小变化，例如通过索引访问数组元素。

对数时间O(log n)：算法执行时间随着输入大小增加而对数增长，例如在排序数组上进行二分查找。

线性时间O(n)：算法执行时间与输入大小线性增长，例如遍历n个元素的数组。

线性对数时间O(n log n)：常见于高效排序算法，例如归并排序和快速排序。

平方时间O(n²)：执行时间与输入大小的平方成正比，例如嵌套循环比较数组中的每个元素。

立方时间O(n³)：执行时间与输入大小的立方成正比，通常出现在有三个嵌套循环的算法中。

指数时间O(2^n)：执行时间随着每个额外元素的增加而翻倍，通常来自递归算法。

阶乘时间O(n!)：执行时间随着输入大小的阶乘增长，常见于生成所有可能排列的算法。

空间复杂度衡量算法相对于输入大小使用的内存量，常见类型包括常数空间O(1)、线性空间O(n)等。

常数空间O(1)：算法使用固定的内存量，例如存储几个变量。

对数空间O(log n)：内存使用量对数增长，通常出现在递归算法中。

线性空间O(n)：内存使用量与输入大小线性增长，例如创建一个大小为n的数组副本。

分析复杂度时应关注循环、递归和数据结构的使用。

时间复杂度关注操作计数，空间复杂度关注额外内存需求。