常见数据结构

数据结构是计算机存储、组织数据的方式。选择合适的数据结构可以提高算法的效率。

线性结构：

• 数组：连续存储，支持随机访问
• 链表：非连续存储，插入删除高效
• 栈：后进先出(LIFO)
• 队列：先进先出(FIFO)

树形结构：

• 二叉树：每个节点最多有两个子节点
• 二叉搜索树：左子树值小于根，右子树值大于根
• AVL树：自平衡二叉搜索树
• 红黑树：近似平衡的二叉搜索树
• B树：多路搜索树，用于文件系统和数据库

图形结构：

• 邻接矩阵：使用二维数组表示图
• 邻接表：使用链表或数组表示图

基础算法

排序算法：

算法	时间复杂度	空间复杂度	稳定性
冒泡排序	O(n²)	O(1)	稳定
快速排序	O(n log n)	O(log n)	不稳定
归并排序	O(n log n)	O(n)	稳定
堆排序	O(n log n)	O(1)	不稳定

查找算法：

• 线性查找：O(n)
• 二分查找：O(log n)，要求有序数组
• 哈希查找：平均O(1)，最坏O(n)

动态规划：

动态规划是一种解决复杂问题的方法，通过将问题分解为子问题并存储子问题的解来避免重复计算。

# 斐波那契数列的动态规划实现
def fibonacci(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]