O(log2n)是什么时间复杂度为常量?

发布网友发布时间：2023-12-01 15:16

共1个回答

热心网友时间：2024-12-04 16:11

根据大O定义易知，O（1） = O（2）。用O(1)和O(2)表示同一个函数时，差别仅在于常数因子c而已。

两个都是时间复杂度为常量。复杂度是用来表达算法的复杂程度跟算法输入的规模N的关系。如果不管N是多大，算法的复杂程度都固定是1或者2（比如1条指令，2个循环），那么在“复杂度”这个概念上，两者都一样，叫做“常数阶”复杂度。

O(g(n)) = { f(n) ：存在这样的正常数c和n0，使得对任意的n >= n0，有0 <= f(n) <= cg(n)成立 }，则g(n)是f(n)的渐进上界。O（g(n)）是指所有与g(n)具有相同增长率或比其增长率小的函数的集合。

扩展资料：

常见的时间复杂度：

按数量级递增排列，常见的时间复杂度有：

常数阶O(1)；对数阶复杂度，即O(log2n)，比如有序数组的二分查找；线性阶O(n)，比如链式表的随机访问；线性对数阶O(nlogn)，比如某些排序算法；平方阶O(n^2)，立方阶O(n^3)等等。有些算法特别复杂，复杂度可能是O(n!)，O(n^n)等等。

k次方阶O(n^k),指数阶O(2^n)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。

参考资料来源：百度百科--时间复杂度