時間複雜度
计算机科学概念 / 維基百科,自由的 encyclopedia
在電腦科學中,演算法的時間複雜度(time complexity)是一個函式,它定性描述該演算法的執行時間。這是一個代表演算法輸入值的字串的長度的函式。時間複雜度常用大O符號表述,不包括這個函式的低階項和首項係數。使用這種方式時,時間複雜度可被稱為是漸近的,亦即考察輸入值大小趨近無窮時的情況。例如,如果一個演算法對於任何大小為 n (必須比 n0 大)的輸入,它至多需要 5n3 + 3n 的時間執行完畢,那麼它的漸近時間複雜度是 O(n3)。
為了計算時間複雜度,我們通常會估計演算法的操作單元數量,每個單元執行的時間都是相同的。因此,總運行時間和演算法的操作單元數量最多相差一個常數係數。
相同大小的不同輸入值仍可能造成演算法的執行時間不同,因此我們通常使用演算法的最壞情況複雜度(英語:Worst-case complexity),記為 T(n) ,定義為任何大小的輸入 n 所需的最大執行時間。另一種較少使用的方法是平均情況複雜度(英語:average-case complexity),通常有特別指定才會使用。時間複雜度可以用函式 T(n) 的自然特性加以分類,舉例來說,有著 T(n) = O(n) 的演算法被稱作「線性時間演算法」;而 T(n) = O(Mn) 和 Mn= O(T(n)) ,其中 M ≥ n > 1 的演算法被稱作「指數時間演算法」。