大 O 表示法
内容提要
本文介绍了大O表示法，用于描述算法效率的标准符号。大O表示法描述了算法的时间复杂度，即算法执行所需的时间，随着输入规模的增加而变化。常见的时间复杂度有恒定时间复杂度O(1)，线性时间复杂度O(n)，二次时间复杂度O(n^2)，对数时间复杂度O(log n)，线性对数时间复杂度O(n log n)。通过计算循环内部代码的执行次数，可以确定算法的时间复杂度。
延伸解读
为什么通常关注最坏情况？
文章指出，大O表示法可以描述最优、平均和最差情况下的时间复杂度，但大部分情况下我们关注的是最坏情况，即时间复杂度函数的上界。这是因为实际应用中，我们更关心算法在最坏情况下的性能表现。例如线性搜索中，即使目标元素可能在数组中间就被找到，但最坏情况下需要遍历整个数组，因此时间复杂度仍为O(n)。
循环嵌套层数与复杂度的关系
文章通过示例说明，单层循环通常对应O(n)，两层嵌套循环对应O(n^2)，三层嵌套循环则对应O(n^3)。每增加一层循环，时间复杂度就增加一次幂。因此，可以通过观察循环的嵌套层数来快速判断算法的大致复杂度，但需注意循环内部操作本身的时间复杂度。
对数复杂度的直观理解
文章以二分查找和循环中变量翻倍为例解释O(log n)。在循环中每次将i乘以2，直到i大于n，循环执行次数约为log₂n。例如n=2000时，循环执行11次，符合log₂(2000)≈11.2877。这种复杂度增长缓慢，即使输入规模很大，执行次数也相对较少。
常见复杂度的性能排序
文章提到，整体上O(n log n)的时间复杂度比O(n^2)好，但比O(n)差。这为比较不同算法提供了参考：O(1)最优，O(log n)次之，O(n)再次，O(n log n)优于O(n^2)。了解这些排序有助于在实际开发中选择合适的算法。
Q&A
大O表示法是什么？
大O表示法是一种用于描述算法效率的标准符号，主要用于表示算法的时间复杂度。
常见的时间复杂度有哪些？
常见的时间复杂度包括O(1)、O(n)、O(n^2)、O(log n)和O(n log n)。
如何确定算法的时间复杂度？
通过计算循环内部代码的执行次数，可以确定算法的时间复杂度。
O(1)和O(n)的区别是什么？
O(1)表示执行时间与输入规模无关，而O(n)表示执行时间与输入规模成正比，随着输入规模线性增长。
什么是对数时间复杂度O(log n)的例子？
二分查找是一个典型的对数时间复杂度O(log n)的例子。
线性对数时间复杂度O(n log n)适用于哪些算法？
一些排序算法，如快速排序和归并排序，具有线性对数时间复杂度O(n log n)。
