常數時間又稱常量時間，在計算複雜度理論中，常量時間是一種時間複雜度。
基本介紹
- 中文名：常數時間
- 又稱：常量時間
- 理論：計算複雜度理論
- 屬於：時間複雜度
- 學科：計算機
- 領域：計算機
簡介,時間複雜度,例子,
簡介
常量時間記為O(1)（採用大O符號）。數字1可以替換為任意常數。
時間複雜度
在計算機科學中，算法的時間複雜度是一個函式，它定性描述該算法的運行時間。這是一個代表算法輸入值的字元串的長度的函式。時間複雜度常用大O符號表述，不包括這個函式的低階項和首項係數。使用這種方式時，時間複雜度可被稱為是漸近的，亦即考察輸入值大小趨近無窮時的情況。例如，如果一個算法對於任何大小為n（必須比n0大）的輸入，它至多需要5n3+ 3n的時間運行完畢，那么它的漸近時間複雜度是 O(n3)。
為了計算時間複雜度，我們通常會估計算法的操作單元數量，每個單元運行的時間都是相同的。因此，總運行時間和算法的操作單元數量最多相差一個常量係數。
相同大小的不同輸入值仍可能造成算法的運行時間不同，因此我們通常使用算法的最壞情況複雜度，記為T(n)，定義為任何大小的輸入n所需的最大運行時間。另一種較少使用的方法是平均情況複雜度，通常有特別指定才會使用。時間複雜度可以用函式T(n) 的自然特性加以分類，舉例來說，有著T(n) =O(n) 的算法被稱作“線性時間算法”；而T(n) =O(Mn) 和Mn= O(T(n)) ，其中M≥n> 1 的算法被稱作“指數時間算法”。
例子
舉例：
- 想在“訪問數組上的元素”的問題上達到常量時間，只要以元素的序號訪問即可。
- 然而“在數組上搜尋最小值”並不是一個常量時間問題，因為這需要掃描數組上的每一個元素以尋找最小值及其位置，一般需要O(n)次訪問。
