查看“︁常數時間”︁的源代码

{{noteTA
|G1=IT
}}

在[[計算複雜度理論]]中，'''常數時間'''是一种[[时间复杂度]]，它表示某个[[算法]]求出解答的时间在固定范围内，而不依照問題輸入資料大小变化。

常數時間記為<math>O(1)</math>（采用[[大O符號]]）。数字1可以替换为任意常数。

舉例：
:想在「存取[[陣列]]上的元素」的問題上達到常數時間，只要以元素的-{zh-hant:序位;zh-hans:序号}-存取即可。
:然而「在陣列上搜索最小值」並不是一個常數時間問題，因為这需要掃描陣列上的每一個元素以寻找最小值及其位置，一般需要<math>O(n)</math>次访问。

==參考文獻==
{{Refbegin|2}}

===書籍===
*{{Citation
| last1=Arora
| first1=Sanjeev
| authorlink1=Sanjeev Arora
| last2=Barak
| first2=Boaz
| title=Computational Complexity: A Modern Approach
| url=http://www.cs.princeton.edu/theory/complexity/
| publisher=[[Cambridge University Press|Cambridge]]
| year=2009
| isbn=978-0-521-42426-4
| zbl=1193.68112
| accessdate=2018-01-19
| archive-date=2021-03-20
| archive-url=https://web.archive.org/web/20210320063128/https://theory.cs.princeton.edu/complexity/
| dead-url=no
}}
* {{Citation
| last1=Downey
| first1=Rod
| last2=Fellows
| first2=Michael
| authorlink2=Michael Fellows
| title=Parameterized complexity
| url=https://www.springer.com/sgw/cda/frontpage/0,11855,5-0-22-1519914-0,00.html?referer=www.springer.de%2Fcgi-bin%2Fsearch_book.pl%3Fisbn%3D0-387-94883-X
| publisher=[[Springer-Verlag]]
| location=Berlin, New York
| year=1999
}}
* {{citation
| last=Du
| first=Ding-Zhu
| author2=Ko, Ker-I
| title=Theory of Computational Complexity
| publisher=[[John Wiley & Sons]]
| year=2000
| isbn=978-0-471-34506-0
}}
* {{Garey-Johnson}}
* {{Citation
| last = Goldreich
| first = Oded
| authorlink = Oded Goldreich
| url = http://www.wisdom.weizmann.ac.il/~oded/cc-book.html
| title = Computational Complexity: A Conceptual Perspective
| publisher = Cambridge University Press
| year = 2008
| accessdate = 2018-01-19
| archive-date = 2021-11-08
| archive-url = https://web.archive.org/web/20211108192437/https://www.wisdom.weizmann.ac.il/~oded/cc-book.html
}}
* {{Citation
| editor1-last=van Leeuwen
| editor1-first=Jan
| editor1-link = Jan van Leeuwen
| title=Handbook of theoretical computer science (vol. A): algorithms and complexity
| publisher=[[MIT Press]]
| isbn=978-0-444-88071-0
| year=1990
}}
* {{citation
 | last = Papadimitriou
 | first = Christos
 | authorlink = Christos Papadimitriou
 | title = Computational Complexity
 | edition = 1st
 | year = 1994
 | publisher = Addison Wesley
 | isbn = 0-201-53082-1
}}
* {{Citation
|last=Sipser
|first=Michael
|authorlink=Michael Sipser
|title=[[Introduction to the Theory of Computation]]
|edition=2nd
|year=2006
|publisher=[[Thomson Learning|Thomson Course Technology]]
|location=USA
|isbn=0-534-95097-3
}}

===研究報告===
* {{Citation | last1=Khalil | first1=Hatem | last2=Ulery | first2=Dana | author2-link=Dana Ulery | title=A Review of Current Studies on Complexity of Algorithms for Partial Differential Equations | publisher=ACM '76 Proceedings of the 1976 Annual Conference | year=1976 | pages=197 | url = http://portal.acm.org/citation.cfm?id=800191.805573 | doi=10.1145/800191.805573 | journal=Proceedings of the annual conference on - ACM 76}}
* {{Citation | last1=Cook | first1=Stephen | author1-link=Stephen Cook | title=An overview of computational complexity | publisher=ACM | year=1983 | journal=Commun. ACM | issn=0001-0782 | volume=26 | issue=6 | pages=400–408 | doi=10.1145/358141.358144 | url=http://www.europrog.ru/paper/sc1982e.pdf | access-date=2018-01-19 | archive-url=https://web.archive.org/web/20180722003012/http://www.europrog.ru/paper/sc1982e.pdf | archive-date=2018-07-22 | dead-url=yes }}
* {{Citation | last1=Fortnow | first1=Lance | last2=Homer | first2=Steven | title=A Short History of Computational Complexity | year=2003 | journal=Bulletin of the EATCS | volume=80 | pages=95–133 | url=http://people.cs.uchicago.edu/~fortnow/papers/history.pdf | accessdate=2018-01-19 | archive-date=2021-03-20 | archive-url=https://web.archive.org/web/20210320063124/http://people.cs.uchicago.edu/~fortnow/papers/history.pdf | dead-url=no }}
* {{Citation | last1=Mertens | first1=Stephan | title=Computational Complexity for Physicists | publisher=IEEE Educational Activities Department | location=Piscataway, NJ, USA | year=2002 | journal=Computing in Science and Eng. | issn=1521-9615 | volume=4 | issue=3 | pages=31–47 | doi=10.1109/5992.998639 | arxiv=cond-mat/0012185}}
{{refend}}

==参见==
{{div col|cols=2}}
*[[多項式時間]]
*[[線性時間]]
*[[指數時間]]
*[[計算複雜度理論]]
*[[P/NP問題]]
*[[NP (複雜度)|NP]]
*[[演算法]]
*[[大O符號]]
{{div col end}}

[[Category:計算複雜性理論]]