常量时间

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

常量时间记为${\displaystyle O(1)}$（采用大O符号）。数字1可以替换为任意常数。

举例：

想在“存取数组上的元素”的问题上达到常量时间，只要以元素的序号存取即可。

然而“在数组上搜索最小值”并不是一个常量时间问题，因为这需要扫描数组上的每一个元素以寻找最小值及其位置，一般需要${\displaystyle O(n)}$次访问。

参考文献

书籍

• Arora, Sanjeev; Barak, Boaz, Computational Complexity: A Modern Approach, Cambridge, 2009 [2018-01-19], ISBN 978-0-521-42426-4, Zbl 1193.68112, （原始内容存档于2021-03-20）
• Downey, Rod; Fellows, Michael, Parameterized complexity, Berlin, New York: Springer-Verlag, 1999
• Du, Ding-Zhu; Ko, Ker-I, Theory of Computational Complexity, John Wiley & Sons, 2000, ISBN 978-0-471-34506-0
• Template:Garey-Johnson
• Goldreich, Oded, Computational Complexity: A Conceptual Perspective, Cambridge University Press, 2008 [2018-01-19], （原始内容存档于2021-11-08）
• van Leeuwen, Jan (编), Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, 1990, ISBN 978-0-444-88071-0
• Papadimitriou, Christos, Computational Complexity 1st, Addison Wesley, 1994, ISBN 0-201-53082-1
• Sipser, Michael, Introduction to the Theory of Computation 2nd, USA: Thomson Course Technology, 2006, ISBN 0-534-95097-3

研究报告

• Khalil, Hatem; Ulery, Dana, A Review of Current Studies on Complexity of Algorithms for Partial Differential Equations, Proceedings of the annual conference on - ACM 76 (ACM '76 Proceedings of the 1976 Annual Conference), 1976: 197, doi:10.1145/800191.805573
• Cook, Stephen, An overview of computational complexity (PDF), Commun. ACM (ACM), 1983, 26 (6): 400–408 [2018-01-19], ISSN 0001-0782, doi:10.1145/358141.358144, （原始内容 (PDF)存档于2018-07-22）
• Fortnow, Lance; Homer, Steven, A Short History of Computational Complexity (PDF), Bulletin of the EATCS, 2003, 80: 95–133 [2018-01-19], （原始内容存档 (PDF)于2021-03-20）
• Mertens, Stephan, Computational Complexity for Physicists, Computing in Science and Eng. (Piscataway, NJ, USA: IEEE Educational Activities Department), 2002, 4 (3): 31–47, ISSN 1521-9615, arXiv:cond-mat/0012185 , doi:10.1109/5992.998639

参见

• 多项式时间
• 线性时间
• 指数时间
• 计算复杂度理论
• P/NP问题
• NP
• 算法
• 大O符号