时间复杂度和空间复杂度是分析算法性能的两个重要指标。

它们用于评估算法在处理输入数据时所需的时间和空间资源。

这些复杂度分析有助于选择最合适的算法和优化程序性能。

一、时间复杂度

时间复杂度衡量了算法执行所需的时间，通常以输入规模 (n) 为变量来表示。它描述了随着输入数据规模的增加，算法的执行时间如何增长。

常见的时间复杂度包括：

①、O(1) - 常数时间复杂度

无论输入数据规模如何，算法的执行时间都保持不变。

例如，访问数组的元素：array[i]。

②、O(log n) - 对数时间复杂度

执行时间随着输入数据规模的增加而以对数方式增长。

例如，二分查找算法：binary_search()。

③、O(n) - 线性时间复杂度

执行时间随着输入数据规模的增加而线性增长。

例如，遍历数组：for (int i = 0; i < n; i++)。

④、O(n log n) - 线性对数时间复杂度

执行时间随着输入数据规模的增加而以 (n \log n) 的方式增长。

例如，快速排序和归并排序：quick_sort() 和 merge_sort()。

⑤、O(n^2) - 平方时间复杂度

执行时间随着输入数据规模的平方增长。

例如，冒泡排序和选择排序：bubble_sort() 和 selection_sort()。

⑥、O(2^n) - 指数时间复杂度

执行时间随着输入数据规模的指数增长。

例如，递归解法的斐波那契数列：fib(n)。

⑦、O(n!) - 阶乘时间复杂度

执行时间随着输入数据规模的阶乘增长。

例如，解决旅行商问题的暴力解法。

二、空间复杂度

空间复杂度衡量了算法执行过程中所需的内存空间。它描述了随着输入数据规模的增加，算法所需的额外内存如何增长。

常见的空间复杂度包括：

①、O(1) - 常数空间复杂度

算法所需的额外内存不随输入数据规模变化。

例如，简单的变量存储：int x;.

②、O(n) - 线性空间复杂度

算法所需的额外内存线性增长。

例如，存储输入数据的数组或链表：int array[n];.

③、O(n^2) - 平方空间复杂度

算法所需的额外内存随着输入数据规模的平方增长。

例如，二维矩阵：int matrix[n][n];.

三、分析实例

3.1、线性查找

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

时间复杂度：O(n)（需要遍历整个数组）

空间复杂度：O(1)（使用了固定数量的额外空间）

3.3、归并排序

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        L = arr[:mid]
        R = arr[mid:]
        merge_sort(L)
        merge_sort(R)
        merge(arr, L, R)

时间复杂度：O(n log n)（分治法，分成两部分，每部分排序需要 O(log n)）

空间复杂度：O(n)（需要额外的空间来存储左右子数组）

四、总结

时间复杂度：描述算法执行所需时间的增长情况。

空间复杂度：描述算法执行所需内存的增长情况。

常见的复杂度形式包括常数、对数、线性、线性对数、平方、指数和阶乘。

复杂度分析帮助理解算法的效率，并在选择算法时做出优化决策。