时间复杂度是什么?

如题所述

根据大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的不断增大,上述时间复杂度不断增大,算法的执行效率越低。

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

温馨提示:答案为网友推荐,仅供参考