时间复杂度与空间复杂度

在算法面试中，理解算法的时间复杂度和空间复杂度是至关重要的。面试官不仅关心你的代码能否正确运行，更关心你的代码效率如何。本章将深入讲解复杂度分析的方法和技巧。

什么是复杂度分析

复杂度分析是评估算法效率的方法，主要包括：

• 时间复杂度：算法执行时间随输入规模增长的趋势
• 空间复杂度：算法所需内存空间随输入规模增长的趋势

时间复杂度

大 O 表示法

大 O 表示法（Big O Notation）用于描述算法的最坏情况时间复杂度。

定义：如果存在正常数 $c$ 和 $n_0$，使得对所有 $n \geq n_0$，有 $T(n) \leq c \cdot f(n)$，则称 $T(n) = O(f(n))$。

常见时间复杂度

O(1) - 常数时间

def get_first_element(arr):
    return arr[0]  # O(1)

O(log n) - 对数时间

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1  # O(log n)

O(n) - 线性时间

def find_max(arr):
    max_val = arr[0]
    for num in arr:
        if num > max_val:
            max_val = num
    return max_val  # O(n)

O(n log n) - 线性对数时间

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])  # O(n log n)
    right = merge_sort(arr[mid:])
    return merge(left, right)

O(n²) - 平方时间

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr  # O(n²)

O(2ⁿ) - 指数时间

def fibonacci_recursive(n):
    if n <= 1:
        return n
    return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)  # O(2ⁿ)

时间复杂度分析技巧

1. 关注最坏情况

def linear_search(arr, target):
    for i, num in enumerate(arr):
        if num == target:
            return i  # 最好情况 O(1)，最坏情况 O(n)
    return -1  # 时间复杂度：O(n)

2. 忽略常数和低阶项

def example(arr):
    # O(1)
    x = arr[0]
    
    # O(n)
    for num in arr:
        print(num)
    
    # O(n)
    for num in arr:
        print(num * 2)
    
    # 总时间复杂度：O(n)，不是 O(2n + 1)

3. 嵌套循环

def nested_loops(n):
    for i in range(n):  # O(n)
        for j in range(n):  # O(n)
            print(i, j)  # O(n²)

4. 递归分析

def recursive_function(n):
    if n <= 1:
        return 1
    return recursive_function(n - 1) + recursive_function(n - 1)  # O(2ⁿ)

空间复杂度

空间复杂度分析算法所需的内存空间。

常见空间复杂度

O(1) - 常数空间

def swap(a, b):
    temp = a  # O(1)
    a = b
    b = temp

O(n) - 线性空间

def copy_array(arr):
    result = []  # O(n)
    for num in arr:
        result.append(num)
    return result

O(n²) - 平方空间

def create_matrix(n):
    matrix = [[0] * n for _ in range(n)]  # O(n²)
    return matrix

空间复杂度分析技巧

1. 输入空间不算入空间复杂度

def process_array(arr):  # arr 是输入，不算入空间复杂度
    result = []  # O(n) 额外空间
    for num in arr:
        result.append(num * 2)
    return result

2. 递归调用栈

def recursive_sum(n):
    if n <= 1:
        return n
    return n + recursive_sum(n - 1)  # O(n) 递归调用栈空间

复杂度优化技巧

1. 使用哈希表优化查找

# 优化前：O(n²)
def two_sum_naive(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

# 优化后：O(n)
def two_sum_optimized(nums, target):
    hash_map = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in hash_map:
            return [hash_map[complement], i]
        hash_map[num] = i
    return []

2. 使用双指针优化

# 优化前：O(n²)
def find_pair_naive(arr, target):
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            if arr[i] + arr[j] == target:
                return [i, j]
    return []

# 优化后：O(n log n)（需要排序）
def find_pair_optimized(arr, target):
    arr.sort()  # O(n log n)
    left, right = 0, len(arr) - 1
    while left < right:
        current_sum = arr[left] + arr[right]
        if current_sum == target:
            return [left, right]
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    return []

3. 使用动态规划优化递归

# 优化前：O(2ⁿ)
def fibonacci_recursive(n):
    if n <= 1:
        return n
    return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)

# 优化后：O(n)
def fibonacci_dp(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

# 进一步优化：O(n) 时间，O(1) 空间
def fibonacci_optimized(n):
    if n <= 1:
        return n
    prev2, prev1 = 0, 1
    for i in range(2, n + 1):
        current = prev1 + prev2
        prev2, prev1 = prev1, current
    return prev1

实际应用

LeetCode 示例

题目：两数之和（Two Sum）

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回它们的数组下标。

解法 1：暴力法

def two_sum_brute_force(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

• 时间复杂度：O(n²)
• 空间复杂度：O(1)

解法 2：哈希表

def two_sum_hash_map(nums, target):
    hash_map = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in hash_map:
            return [hash_map[complement], i]
        hash_map[num] = i
    return []

• 时间复杂度：O(n)
• 空间复杂度：O(n)

总结

复杂度分析是算法面试中的核心技能：

1. 时间复杂度：关注算法执行时间随输入规模的增长趋势
2. 空间复杂度：关注算法所需内存空间随输入规模的增长趋势
3. 优化技巧：使用哈希表、双指针、动态规划等方法优化复杂度
4. 实际应用：在解题时始终考虑复杂度，选择最优解法

掌握复杂度分析不仅能帮助你在面试中更好地评估算法效率，还能指导你选择合适的数据结构和算法。

接下来，让我们学习数组与字符串，这是最基础也是最重要的数据结构之一。