常數時間

常數時間又稱常量時間,在計算複雜度理論中,常量時間是一種時間複雜度。

基本信息

簡介

在計算複雜度理論中, 常量時間是一種時間複雜度,它表示某個算法求出解答的時間在固定範圍內,而不依照問題輸入數據大小變化。

常量時間記為O(1)(採用大O符號)。數字1可以替換為任意常數。

時間複雜度

在計算機科學中,算法的 時間複雜度是一個函式,它定性描述該算法的運行時間。這是一個代表算法輸入值的字元串的長度的函式。時間複雜度常用大O符號表述,不包括這個函式的低階項和首項係數。使用這種方式時,時間複雜度可被稱為是漸近的,亦即考察輸入值大小趨近無窮時的情況。例如,如果一個算法對於任何大小為 n(必須比 n大)的輸入,它至多需要5 n+ 3 n的時間運行完畢,那么它的漸近時間複雜度是 O( n)。

為了計算時間複雜度,我們通常會估計算法的操作單元數量,每個單元運行的時間都是相同的。因此,總運行時間和算法的操作單元數量最多相差一個常量係數。

相同大小的不同輸入值仍可能造成算法的運行時間不同,因此我們通常使用算法的最壞情況複雜度,記為 T(n),定義為任何大小的輸入 n所需的最大運行時間。另一種較少使用的方法是平均情況複雜度,通常有特別指定才會使用。時間複雜度可以用函式 T( n) 的自然特性加以分類,舉例來說,有著 T( n) = O( n) 的算法被稱作“線性時間算法”;而 T( n) = O( M) 和 M= O( T( n)) ,其中 M≥ n> 1 的算法被稱作“指數時間算法”。

例子

舉例:

想在“訪問數組上的元素”的問題上達到常量時間,只要以元素的序號訪問即可。

然而“在數組上搜尋最小值”並不是一個常量時間問題,因為這需要掃描數組上的每一個元素以尋找最小值及其位置,一般需要O(n)次訪問。

相關詞條

熱門詞條

聯絡我們