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)表示操作的执行时间与输入规模和其对数的乘积成正比，常见于某些排序算法。
- 确定算法的时间复杂度通常通过计算循环内部代码的执行次数来实现。
❓
延伸问答
大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)。
➡️
