DEV Community
·
第2天：常见的时间复杂度
💡
原文英文，约1300词，阅读约需5分钟。
📝
内容提要
时间复杂度是算法运行时间随输入规模增加而增加的度量，常见的时间复杂度有O(1)、O(log n)、O(n)、O(n log n)、O(n²)和O(2ⁿ)。空间复杂度是算法运行时使用的内存量。排序算法如冒泡排序、选择排序和插入排序的时间复杂度为O(n²)，不适用于大规模输入。
🎯
关键要点
- 时间复杂度是算法运行时间随输入规模增加而增加的度量。
- 常见的时间复杂度有O(1)、O(log n)、O(n)、O(n log n)、O(n²)和O(2ⁿ)。
- O(1)表示常数时间复杂度，执行时间与输入规模无关。
- O(log n)表示对数时间复杂度，常见于将问题分解为更小子问题的算法，如二分查找。
- O(n)表示线性时间复杂度，运行时间与输入规模成正比。
- O(n log n)是线性和对数时间复杂度的组合，常见于高效排序算法，如归并排序和快速排序。
- O(n²)表示平方时间复杂度，通常出现在嵌套循环中，效率较低。
- O(2ⁿ)表示指数时间复杂度，随着输入数据的增加，算法的增长速度加倍，适用于小规模输入。
- 空间复杂度是算法运行时使用的内存量，包括辅助空间和输入空间。
- 时间复杂度和空间复杂度的主要区别在于关注的方面：时间复杂度关注运行时间，空间复杂度关注内存使用。
- 冒泡排序、选择排序和插入排序的时间复杂度为O(n²)，不适用于大规模输入。
➡️
