算法时间复杂度o(1)和o(2)的区别???
O后面的括号中有一个函数,指明某个算法的耗时/耗空间与数据增长量之间的关系。其中的n代表输入数据的量。
时间复杂度为O(n),就代表数据量增大几倍,耗时也增大几倍。比如常见的遍历算法。所以O(2)相比于O(1)数据量会更多,同时需要执行的时间会更多。
一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),存在一个正常数c使得fn*c>=T(n)恒成立。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。
扩展资料
时间复杂度O(n^2),就代表数据量增大n倍时,耗时增大n的平方倍,这是比线性更高的时间复杂度。比如冒泡排序,就是典型的O(n^2)的算法,对n个数排序,需要扫描n×n次。
比如O(logn),当数据增大n倍时,耗时增大logn倍(这里的log是以2为底的,比如,当数据增大256倍时,耗时只增大8倍,是比线性还要低的时间复杂度)。二分查找就是O(logn)的算法,每找一次排除一半的可能,256个数据中查找只要找8次就可以找到目标。
O(nlogn)同理,就是n乘以logn,当数据增大256倍时,耗时增大256*8=2048倍。这个复杂度高于线性低于平方。归并排序就是O(nlogn)的时间复杂度。
参考资料来源:百度百科—算法复杂度
根据大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的不断增大,上述时间复杂度不断增大,算法的执行效率越低。
参考资料来源:
本回答被网友采纳1,log(2)n,n,n log(2)n ,n的平方,n的三次方,2的n次方,n!
1指的是常数。即,无论算法的输入n是多大,都不会影响到算法的运行时间。这种是最优的算法。而n!(阶乘)是非常差的算法。当n变大时,算法所需的时间是不可接受的。
用通俗的话来描述,我们假设n=1所需的时间为1秒。那么当n = 10,000时。
O(1)的算法需要1秒执行完毕。
O(n)的算法需要10,000秒 ≈ 2.7小时 执行完毕。
O(n2)的算法需要100,000,000秒 ≈ 3.17年 执行完毕。
O(n!)的算法需要XXXXXXXX(系统的计算器已经算不出来了)。
可见算法的时间复杂度影响有多大。
所以O(1)和O(n)差了2.7小时,区别显而易见。本回答被网友采纳