DEV Community
·
彻底掌握大O符号
💡
原文英文，约2200词，阅读约需8分钟。
📝
内容提要
本文介绍了大O时间复杂度的概念，分析了算法在输入规模增长时的运行时间，并通过示例解释了不同复杂度（如O(n)、O(1)、O(n^2)）以帮助读者理解算法效率。作者希望通过总结复习提升面试表现。
🎯
关键要点
- 大O时间复杂度用于分类算法，根据输入规模增长时的运行时间或空间需求。
- O(n)表示线性增长，示例为查找数组中的最大值。
- O(1)表示常数时间复杂度，示例为返回数组的第一个元素。
- O(n^2)表示嵌套循环的时间复杂度，示例为计算两个骰子的所有组合。
- O(n*m)表示两个不同大小的骰子的组合计算。
- O(log n)用于二分搜索，运行时间增长缓慢。
- O(n log n)常见于排序算法，如归并排序。
- O(2^n)通常出现在递归算法中，如斐波那契数列。
- O(n!)表示阶乘复杂度，常见于排列问题，效率极低。
❓
延伸问答
什么是大O时间复杂度？
大O时间复杂度用于分类算法，描述算法在输入规模增长时的运行时间或空间需求。
O(n)和O(1)的区别是什么？
O(n)表示线性增长，运行时间随输入规模线性增加；O(1)表示常数时间复杂度，运行时间不随输入规模变化。
O(n^2)的典型示例是什么？
O(n^2)通常出现在嵌套循环中，例如计算两个骰子的所有组合。
O(log n)的应用场景有哪些？
O(log n)常用于二分搜索，适用于在已排序数组中查找特定值的场景。
O(n log n)通常出现在什么算法中？
O(n log n)常见于排序算法，如归并排序。
O(2^n)和O(n!)的复杂度有什么区别？
O(2^n)通常出现在递归算法中，而O(n!)表示阶乘复杂度，效率极低，常见于排列问题。
➡️
