DEV Community
·
O符号
💡
原文英文，约200词，阅读约需1分钟。
📝
内容提要
O符号用于通过描述算法完成所需的时间来衡量算法的效率。根据所使用的符号，可以预期不同类型的行为，例如常数时间、线性时间、对数时间、二次时间、指数时间、阶乘时间和对数线性时间。
🎯
关键要点
-
O符号用于描述算法完成所需的时间，衡量算法的效率。
-
算法的效率通常通过处理N个输入的速度来定义。
-
O(1) - 常数时间，算法对n个输入的完成时间相同。
-
O(n) - 线性时间，完成时间随着n的增加而增加。
-
O(log n) - 对数时间，完成时间随着n的对数增加。
-
O(n^2) - 二次时间，完成时间随着n的平方增加。
-
O(2^n) - 指数时间，完成时间呈指数增长。
-
O(n!) - 阶乘时间，完成步骤随着输入的阶乘增加。
-
O(nlogn) - 对数线性时间，logn操作将发生n次。
❓
延伸问答
O符号是什么？
O符号用于描述算法完成所需的时间，衡量算法的效率。
O(1)和O(n)有什么区别？
O(1)表示常数时间，算法完成时间不随输入数量变化；O(n)表示线性时间，完成时间随着输入数量增加而增加。
O(log n)表示什么？
O(log n)表示对数时间，完成时间随着输入数量的对数增加。
O(n^2)的时间复杂度如何影响算法效率？
O(n^2)表示二次时间，完成时间随着输入数量的平方增加，这通常会导致效率较低。
什么是O(nlogn)时间复杂度？
O(nlogn)表示对数线性时间，logn操作将发生n次，通常用于高效排序算法。
O(2^n)和O(n!)的时间复杂度有什么不同？
O(2^n)表示指数时间，完成时间呈指数增长；O(n!)表示阶乘时间，完成步骤随着输入的阶乘增加，通常更为复杂。
➡️
