深入浅出理解时间复杂度和空间复杂度-CSDN博客

def binary_search(arr, target):
    low, high = 0, len(arr)-1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

O(n) - 线性时间

执行时间与数据量成正比
例子：遍历数组

python

复制

下载

def find_max(arr):
    max_val = arr[0]
    for num in arr:  # 遍历所有元素
        if num > max_val:
            max_val = num
    return max_val

O(n log n) - 线性对数时间
- 比线性慢，但比平方快
- 例子：快速排序、归并排序
python

复制

下载
```
# 快速排序的复杂度为O(n log n)
```

O(n²) - 平方时间

数据量翻倍，时间变为4倍
例子：嵌套循环

python

复制

下载

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):         # 外层循环n次
        for j in range(n-1):   # 内层循环n-1次
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

O(2ⁿ) - 指数时间
- 数据量增加1，时间翻倍
- 例子：斐波那契数列递归解法
python

复制

下载
```
def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n-1) + fibonacci(n-2)
```
O(n!) - 阶乘时间
- 最慢的复杂度之一
- 例子：旅行商问题的暴力解法

空间复杂度常见情况

O(1) - 常数空间
- 算法使用的额外空间不随输入规模变化
- 例子：交换两个变量
python

复制

下载
```
def swap(a, b):
    temp = a  # 只用了1个额外变量
    a = b
    b = temp
```

O(n) - 线性空间

额外空间与输入规模成正比
例子：复制数组

python

复制

下载

def copy_array(arr):
    new_arr = []  # 创建与输入等大的新数组
    for num in arr:
        new_arr.append(num)
    return new_arr

O(n²) - 平方空间
- 额外空间与输入规模的平方成正比
- 例子：构建二维矩阵
python

复制

下载
```
def create_matrix(n):
    matrix = [[0]*n for _ in range(n)]  # n×n的矩阵
    return matrix
```

O(log n) - 对数空间

递归调用时的栈空间
例子：二分查找的递归实现

python

复制

下载

def binary_search_recursive(arr, target, low, high):
    if low > high:
        return -1
    mid = (low + high) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid+1, high)
    else:
        return binary_search_recursive(arr, target, low, mid-1)

三、如何分析复杂度

时间复杂度分析步骤

找出基本操作（通常是循环内的操作）
计算基本操作的执行次数与n的关系
忽略低阶项和常数系数

示例分析：

python

复制

下载

def example(n):
    sum = 0                 # O(1)
    for i in range(n):      # 循环n次
        sum += i            # O(1)的操作执行n次 → O(n)
    return sum              # O(1)

总时间复杂度：O(1) + O(n) + O(1) = O(n)

空间复杂度分析步骤

计算算法使用的额外存储空间（不包括输入数据本身）
考虑变量、数据结构、递归调用栈等

示例分析：

python

复制

下载

def example(n):
    arr = [0]*n      # 创建了长度为n的数组 → O(n)
    for i in range(n):
        arr[i] = i
    return arr

总空间复杂度：O(n)（因为创建了大小为n的数组）

四、复杂度对比图表

时间复杂度增长趋势

复制

下载

n       O(1)  O(log n)  O(n)  O(n log n)  O(n²)  O(2ⁿ)    O(n!)
-----------------------------------------------------------------
1       1     0         1     0           1      2        1
10      1     ~3.3      10    ~33         100    1024     ~3.6e6
100     1     ~6.6      100   ~664        10,000 1.27e30  9.33e157

常见算法复杂度汇总

算法	时间复杂度(平均)	时间复杂度(最坏)	空间复杂度
线性查找	O(n)	O(n)	O(1)
二分查找	O(log n)	O(log n)	O(1)
冒泡排序	O(n²)	O(n²)	O(1)
快速排序	O(n log n)	O(n²)	O(log n)
归并排序	O(n log n)	O(n log n)	O(n)
哈希表查找	O(1)	O(n)	O(n)
深度优先搜索(DFS)	O(V+E)	O(V+E)	O(V)
广度优先搜索(BFS)	O(V+E)	O(V+E)	O(V)