常數時間
在計算複雜度理論中，常數時間是一种时间复杂度，它表示某个算法求出解答的时间在固定范围内，而不依照問題輸入資料大小变化。
常數時間記為（采用大O符號）。数字1可以替换为任意常数。
舉例：
- 想在「存取陣列上的元素」的問題上達到常數時間，只要以元素的存取即可。
- 然而「在陣列上搜索最小值」並不是一個常數時間問題，因為这需要掃描陣列上的每一個元素以寻找最小值及其位置，一般需要次访问。
參考文獻
書籍
- Arora, Sanjeev; Barak, Boaz, , Cambridge, 2009, ISBN 978-0-521-42426-4, Zbl 1193.68112
- Downey, Rod; Fellows, Michael, , Berlin, New York: Springer-Verlag, 1999
- Du, Ding-Zhu; Ko, Ker-I, , John Wiley & Sons, 2000, ISBN 978-0-471-34506-0
- Template:Garey-Johnson
- Goldreich, Oded, , Cambridge University Press, 2008
- van Leeuwen, Jan (编), , MIT Press, 1990, ISBN 978-0-444-88071-0
- Papadimitriou, Christos, 1st, Addison Wesley, 1994, ISBN 0-201-53082-1
- Sipser, Michael, 2nd, USA: Thomson Course Technology, 2006, ISBN 0-534-95097-3
研究報告
- Khalil, Hatem; Ulery, Dana, , 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, (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, (PDF), Bulletin of the EATCS, 2003, 80: 95–133
- Mertens, Stephan, , 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
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.