LeetCode 算法复杂度分析与优化技巧

VocabVictor2024-09-022024-09-04

引言

在解决 LeetCode 问题时,除了得到正确的结果,算法的效率也是至关重要的。这涉及到时间复杂度和空间复杂度的分析与优化。本文将深入探讨如何分析算法复杂度,以及一些常用的优化技巧,帮助你在 LeetCode 上编写出更高效的解决方案。

1. 复杂度分析基础

1.1 时间复杂度

时间复杂度用于描述算法运行时间与输入规模之间的关系。常见的时间复杂度有:

O(1): 常数时间
O(log n): 对数时间
O(n): 线性时间
O(n log n): 线性对数时间
O(n^2), O(n^3): 多项式时间
O(2^n), O(n!): 指数时间

1.2 空间复杂度

空间复杂度用于描述算法所需额外空间与输入规模之间的关系。常见的空间复杂度有:

O(1): 常数空间
O(n): 线性空间
O(n^2): 平方空间

1.3 如何分析复杂度

确定输入规模 n
找出算法的基本操作
计算基本操作的执行次数与 n 的关系
选择增长最快的项并去除常数因子

2. 时间复杂度优化技巧

2.1 选择合适的数据结构

不同的数据结构在不同操作上有各自的优势:

数组: 随机访问 O(1)
链表: 插入和删除 O(1)
哈希表: 平均查找、插入、删除 O(1)
二叉搜索树: 平均查找、插入、删除 O(log n)

例如,LeetCode 1. Two Sum 可以使用哈希表优化:

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        num_dict = {}
        for i, num in enumerate(nums):
            complement = target - num
            if complement in num_dict:
                return [num_dict[complement], i]
            num_dict[num] = i
        return []

2.2 使用更高效的算法

排序: 选择更快的排序算法,如快速排序(O(n log n))而不是冒泡排序(O(n^2))
搜索: 使用二分搜索(O(log n))而不是线性搜索(O(n))

例如,LeetCode 33. Search in Rotated Sorted Array 使用二分搜索:

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                return mid
            
            if nums[left] <= nums[mid]:
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            else:
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1
        
        return -1

2.3 预处理和缓存

预计算: 提前计算并存储一些值
记忆化: 存储已计算的结果以避免重复计算

例如,LeetCode 70. Climbing Stairs 使用动态规划:

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        dp = [0] * (n + 1)
        dp[1] = 1
        dp[2] = 2
        for i in range(3, n + 1):
            dp[i] = dp[i-1] + dp[i-2]
        return dp[n]

2.4 避免不必要的计算

提前终止: 当找到解或确定无解时立即返回
剪枝: 在搜索或回溯中跳过不必要的分支

例如,LeetCode 79. Word Search 使用回溯和剪枝:

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        def dfs(i, j, k):
            if k == len(word):
                return True
            if (i < 0 or i >= len(board) or 
                j < 0 or j >= len(board[0]) or 
                board[i][j] != word[k]):
                return False
            
            temp = board[i][j]
            board[i][j] = '#'  # mark as visited
            
            result = (dfs(i+1, j, k+1) or 
                      dfs(i-1, j, k+1) or 
                      dfs(i, j+1, k+1) or 
                      dfs(i, j-1, k+1))
            
            board[i][j] = temp  # restore
            return result
        
        for i in range(len(board)):
            for j in range(len(board[0])):
                if dfs(i, j, 0):
                    return True
        return False

3. 空间复杂度优化技巧

3.1 原地修改

尽可能在原数组上进行修改,而不是创建新的数组。

例如,LeetCode 283. Move Zeroes:

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        non_zero = 0
        for i in range(len(nums)):
            if nums[i] != 0:
                nums[non_zero], nums[i] = nums[i], nums[non_zero]
                non_zero += 1

3.2 使用常数额外空间

尽量使用有限的变量而不是额外的数据结构。

例如,LeetCode 121. Best Time to Buy and Sell Stock:

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:
            return 0
        
        min_price = float('inf')
        max_profit = 0
        
        for price in prices:
            min_price = min(min_price, price)
            current_profit = price - min_price
            max_profit = max(max_profit, current_profit)
        
        return max_profit

3.3 复用空间

在某些情况下,可以复用已有的空间来存储中间结果。

例如,LeetCode 338. Counting Bits:

class Solution:
    def countBits(self, n: int) -> List[int]:
        ans = [0] * (n + 1)
        for i in range(1, n + 1):
            ans[i] = ans[i >> 1] + (i & 1)
        return ans

3.4 位操作

使用位操作可以在一个整数中存储多个信息,从而减少空间使用。

例如,LeetCode 191. Number of 1 Bits:

class Solution:
    def hammingWeight(self, n: int) -> int:
        count = 0
        while n:
            n &= (n - 1)
            count += 1
        return count

4. 平衡时间和空间复杂度

在某些情况下,我们需要在时间和空间复杂度之间做出权衡。常见的策略包括:

空间换时间: 使用额外的空间来存储中间结果,从而减少计算时间
时间换空间: 通过增加计算来减少存储需求

例如,LeetCode 146. LRU Cache 中,我们使用哈希表和双向链表来实现 O(1) 的时间复杂度,但代价是 O(n) 的空间复杂度:

class Node:
    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity: int):
        self.cache = {}
        self.capacity = capacity
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head

    def get(self, key: int) -> int:
        if key in self.cache:
            node = self.cache[key]
            self._remove(node)
            self._add(node)
            return node.value
        return -1

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self._remove(self.cache[key])
        node = Node(key, value)
        self._add(node)
        self.cache[key] = node
        if len(self.cache) > self.capacity:
            lru = self.head.next
            self._remove(lru)
            del self.cache[lru.key]

    def _remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def _add(self, node):
        node.prev = self.tail.prev
        node.next = self.tail
        self.tail.prev.next = node
        self.tail.prev = node