常量时间

计算复杂度理论中,常量时间是一种时间复杂度,它表示某个算法求出解答的时间在固定范围内,而不依照问题输入资料大小变化。

常量时间记为(采用大O符号)。数字1可以替换为任意常数。

举例:

想在“存取数组上的元素”的问题上达到常量时间,只要以元素的序号存取即可。
然而“在数组上搜索最小值”并不是一个常量时间问题,因为这需要扫描数组上的每一个元素以寻找最小值及其位置,一般需要次访问。

参考文献

书籍

研究报告

参见