大约 3 分钟
数据结构与算法课程内容包括数据结构与抽象数据类型、算法特性及分类、算法效率与度量、线性结构、顺序表、链表、栈与队列、栈与递归、递归转非递归、> 字符串的存储结构、字符串运算的算法实现、字符串的快速模式匹配、二叉树的抽象数据类型、二叉树的搜索、二叉树的存储结构、树与二叉树的等价转换、树> 的抽象数据类型及树的遍历、树的链式存储结构、树的父指针表示法、树的顺序存储和 K 叉树、图的概念和抽象数据类型、图的存储结构、图的遍历、内排> > 序、检索等内容。
学习文档
算法复杂度
算法复杂度通常用来描述算法执行效率（时间复杂度）和所需存储资源（空间复杂度）。理解算法复杂度有助于我们评估算法在实际应用中的性能。
时间复杂度
时间复杂度是对算法执行时间的估计，描述了输入规模 𝑛 增大时，算法的运行时间如何变化。以下是常见的时间复杂度级别，从低到高：
- O(1) - 常数时间
- 运行时间与输入规模无关，直接输出结果。
- 示例：数组访问元素。
- O(log𝑛) - 对数时间
- 每次操作将问题规模减小一半。
- 示例：二分查找。
- O(n) - 线性时间
- 运行时间与输入规模成正比。
- 示例：遍历数组。
- O(n·log𝑛) - 线性对数时间
- 常见于分治算法。
- 示例：快速排序、归并排序。
- O(n^2) - 二次时间
- 双重循环中常见。
- 示例：冒泡排序、选择排序。
- O(n^k) - 多项式时间
𝑘k 次嵌套循环。- 示例：矩阵乘法。
- O(2^n) - 指数时间
- 常见于递归解决方案，枚举所有可能。
- 示例：解决子集问题、斐波那契数列（未优化）。
- O(n!) - 阶乘时间
- 常见于排列问题。
- 示例：旅行商问题暴力解法。
空间复杂度
空间复杂度描述了算法运行时所需的额外存储空间，通常包括临时变量、递归栈等：
- O(1) - 常数空间：不依赖输入规模，使用固定空间。
- O(n) - 线性空间：与输入规模成正比。
- O(n^2) - 二次空间：需要二维存储，例如矩阵操作。
算法优化
- 时间复杂度优化
- 使用合适的数据结构（如哈希表、优先队列）。
- 改进算法逻辑（如动态规划代替递归）。
- 降低循环层数，优化条件判断。
- 空间复杂度优化
- 原地操作减少额外空间需求。
- 使用懒加载或流式处理避免整体存储。
常见排序算法与实现
Todoist