算法复杂度分析 🧠

在编程与算法学习中，复杂度分析是评估代码效率的核心技能！通过分析，我们可以判断算法在极端情况下的表现，从而优化性能。以下是关键知识点：

时间复杂度 ⏱️

• 定义：衡量算法执行时间随输入规模增长的变化趋势
• 常见类型：
  • 常数时间 $O(1)$：如直接访问数组元素
  • 对数时间 $O(\log n)$：如二分查找
  • 线性时间 $O(n)$：如遍历链表
  • 平方时间 $O(n^2)$：如双重循环
• 大O符号：忽略常数因子，只关注增长趋势（如 O(n^2) 比 10n^2 更重要）

空间复杂度 📦

• 定义：评估算法所需额外内存空间
• 典型场景：
  • 原地排序（如快速排序）：$O(1)$
  • 分治算法（如归并排序）：$O(n)$
  • 递归调用栈：$O(\log n)$ 或 $O(n)$
• 注意事项：空间复杂度通常低于时间复杂度，但需关注内存限制

实战技巧 💡

1. 用 for 循环计算时间复杂度
2. 分析递归函数的调用次数
3. 注意隐式空间（如栈空间）
4. 使用 主定理 简化分治算法分析

延伸学习：算法类型大全 | 数据结构与复杂度