从时间与空间的角度看算法：复杂度的权衡与应用

Author： kared
发布时间：June 5, 2023
11 views
No comments
2585 words
Categories：算法刷题

在计算机科学中，算法的性能通常通过**时间复杂度**和**空间复杂度**来衡量。这两个概念是评估算法效率的重要指标，帮助开发者选择合适的算法和数据结构。

## 什么是时间复杂度？

时间复杂度是指算法执行所需时间的量度。它通常用大 O 表示法来描述，表示输入规模（通常用 n 表示）与算法执行时间之间的关系。常见的时间复杂度包括：

- **O(1)**：常数时间复杂度，算法执行时间不随输入规模变化。
- **O(log n)**：对数时间复杂度，常见于二分查找等算法。
- **O(n)**：线性时间复杂度，算法执行时间与输入规模成正比。
- **O(n log n)**：线性对数时间复杂度，常见于高效排序算法，如归并排序和快速排序。
- **O(n^2)**：平方时间复杂度，通常出现在简单的嵌套循环中。

## 什么是空间复杂度？

空间复杂度是指算法执行所需内存空间的量度，也用大 O 表示法来描述。它考虑了算法在运行过程中所需的额外空间，包括临时变量、数据结构等。常见的空间复杂度包括：

- **O(1)**：常数空间复杂度，算法使用的额外空间不随输入规模变化。
- **O(n)**：线性空间复杂度，额外空间与输入规模成正比。
- **O(n^2)**：平方空间复杂度，通常在处理二维数组或矩阵时出现。

## 时间复杂度与空间复杂度的权衡

时间复杂度和空间复杂度是评估算法性能的关键指标。在选择算法时，时间复杂度和空间复杂度之间往往存在权衡，通过合理的权衡，可以在性能和资源使用之间找到最佳平衡点。例如，某些算法可能在时间上更高效，但需要更多的内存；而另一些算法可能在空间上更节省，但执行时间较长。开发者需要根据具体问题和环境选择最合适的算法。

## 算法开源书籍推荐

在深入理解时间复杂度和空间复杂度的过程中，参考一些权威的文献和资源将大有裨益。以下两篇文章提供了清晰而全面的阐述，适合希望深入学习这一主题的读者。

第一篇文章来自《Hello 算法》，详细介绍了计算复杂度的基本概念、常见类型以及如何在实际算法中应用这些知识，帮助读者建立扎实的理论基础。可以通过以下链接访问：[Hello Algo - 计算复杂度](https://www.hello-algo.com/chapter_computational_complexity/)。

开源书籍地址：[:tada: GitHub - krahets/hello-algo](https://github.com/krahets/hello-algo)

第二篇文章是来自《LeetCode Cookbook》，专注于时间复杂度的具体应用和实例，适合希望通过实际案例加深理解的开发者。您可以通过以下链接进行阅读：[LeetCode Cookbook - 时间复杂度](https://books.halfrost.com/leetcode/ChapterOne/Time_Complexity/)。

开源书籍地址：[:tada: GitHub - halfrost/LeetCode-Go](https://github.com/halfrost/LeetCode-Go)

## 通过数据范围反推算法复杂度

🔍 内容转载来自 [AcWing - 由数据范围反推算法复杂度以及算法内容](https://www.acwing.com/blog/content/32/) 
</div>

在ACM竞赛或笔试中，题目的时间限制通常为1秒或2秒。在这种情况下，C++代码中的操作次数控制在 $10^7$ 到 $10^8$ 之间是最佳选择。下面是针对不同数据范围的时间复杂度和算法选择建议：

1. **$n \leq 30$**：适合使用指数级别的算法，如深度优先搜索（DFS）加剪枝和状态压缩动态规划（DP）。
2. **$n \leq 10^2$**：可以使用 $O(n^3)$ 的算法，如Floyd算法、动态规划和高斯消元。
3. **$n \leq 10^3$**：适合使用 $O(n^2)$ 或 $O(n^2 \log n)$ 的算法，包括动态规划、二分查找、朴素版Dijkstra、朴素版Prim和Bellman-Ford算法。
4. **$n \leq 10^4$**：可以考虑 $O(n \sqrt{n})$ 的算法，如块状链表、分块和莫队算法。
5. **$n \leq 10^5$**：适合使用 $O(n \log n)$ 的算法，包括各种排序、线段树、树状数组、集合/映射、堆、拓扑排序、Dijkstra（配合堆）、Prim（配合堆）、Kruskal、SPFA、求凸包、半平面交、二分查找、CDQ分治、整体二分、后缀数组、树链剖分和动态树。
6. **$n \leq 10^6$**：可以使用 $O(n)$ 或 $O(n \log n)$ 的算法，如单调队列、哈希、双指针扫描、并查集、KMP、AC自动机，以及常数比较小的 $O(n \log n)$ 算法（如排序、树状数组、堆、Dijkstra和SPFA）。
7. **$n \leq 10^7$**：适合使用 $O(n)$ 的算法，如双指针扫描、KMP、AC自动机和线性筛法求素数。
8. **$n \leq 10^9$**：可以使用 $O(\sqrt{n})$ 的算法，适合判断质数。
9. **$n \leq 10^{18}$**：适合使用 $O(\log n)$ 的算法，如求最大公约数、快速幂和数位动态规划。
10. **$n \leq 10^{1000}$**：可以使用 $O((\log k)^2)$ 的算法，其中 $k$ 表示位数，适合高精度加减乘除。
11. **$n \leq 10^{100000}$**：适合使用 $O(\log k \times \log \log k)$ 的算法，其中 $k$ 表示位数，适合高精度加减和FFT/NTT。

这些建议可以帮助您在编写算法时更有效地选择合适的时间复杂度。

Last modification：August 4, 2024