为什么哈希表的时间复杂度是常数阶O(1)？哈希表时间复杂度

时间复杂度常数阶为什么只能为0（1）？

时间复杂度O是一个上界，设算法所需时间和数据规模n的关系为t(n)，如果当n->∞时，总有O*c>t(n)成立，其中c为一个常数，则记O为算法的时间复杂度。

如果你的算法只包含固定的打印语句，和数据规模没有关系，那么算法就是常量时间复杂度O(1)。哪怕你的算法打印语句有10000行，也可以找到常数c=10001，使得1*10001>10000成立，因此算法的时间复杂度仍然是O(1)。

O(1)说明不管x、y同时增大多少倍，这段代码都能在常数时间结束运行

其实这段代码不能简单的说复杂度是O(1)

说是O(10y)=O(y)更准确

x的大小对总体复杂度影响不大

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)的时间复杂度。

参考资料来源：百度百科—算法复杂度

最早是由德国数学家Paul Bachmann在1894年首先使用的，之后又被另一位德国数学家Edmund Landau在其作品中广泛使用，因此也叫做Landau symbol（朗道符号）。真正在计算机领域被用于复杂度计算还得归功于传奇的Donald Knuth，Omega符号也是他引入的。