Cubik的小站
·
大 O 表示法
💡
原文中文，约5700字，阅读约需14分钟。
📝
内容提要
本文介绍了大O表示法，用于描述算法效率的标准符号。大O表示法描述了算法的时间复杂度，即算法执行所需的时间，随着输入规模的增加而变化。常见的时间复杂度有恒定时间复杂度O(1)，线性时间复杂度O(n)，二次时间复杂度O(n^2)，对数时间复杂度O(log n)，线性对数时间复杂度O(n log n)。通过计算循环内部代码的执行次数，可以确定算法的时间复杂度。
🎯
关键要点
- 大O表示法用于描述算法的效率，特别是时间复杂度。
- 时间复杂度描述算法执行所需的时间如何随着输入规模的增加而变化。
- 常见的时间复杂度包括O(1)、O(n)、O(n^2)、O(log n)和O(n log n)。
- O(1)表示操作的执行时间与输入规模无关，执行时间是常数。
- O(n)表示操作的执行时间与输入规模成正比，随着输入规模线性增长。
- O(n^2)表示操作的执行时间与输入规模的平方成正比，通常涉及嵌套循环。
- O(log n)表示操作的执行时间与输入规模的对数成正比，典型例子是二分查找。
- O(n log n)表示操作的执行时间与输入规模和其对数的乘积成正比，常见于某些排序算法。
- 确定算法的时间复杂度通常通过计算循环内部代码的执行次数来实现。
➡️
