時間復(fù)雜度是什么意思?

在計(jì)算機(jī)科學(xué)中，時間復(fù)雜性，又稱時間復(fù)雜度，算法的時間復(fù)雜度是一個函數(shù)，它定性描述該算法的運(yùn)行時間。這是一個代表算法輸入值的字符串的長度的函數(shù)。時間復(fù)雜度常用大O符號表述，不包括這個函數(shù)的低階項(xiàng)和首項(xiàng)系數(shù)。使用這種方式時，時間復(fù)雜度可被稱為是漸近的，亦即考察輸入值大小趨近無窮時的情況。為了計(jì)算時間復(fù)雜度，我們通常會估計(jì)算法的操作單元數(shù)量，每個單元運(yùn)行的時間都是相同的。因此，總運(yùn)行時間和算法的操作單元數(shù)量最多相差一個常量系數(shù)。相同大小的不同輸入值仍可能造成算法的運(yùn)行時間不同，因此我們通常使用算法的最壞情況復(fù)雜度，記為T(n)，定義為任何大小的輸入n所需的最大運(yùn)行時間。另一種較少使用的方法是平均情況復(fù)雜度，通常有特別指定才會使用。時間復(fù)雜度可以用函數(shù)T(n) 的自然特性加以分類，舉例來說，有著T(n) =O(n) 的算法被稱作“線性時間算法”;而T(n) =O(M^n) 和M= O(T(n)) ，其中M≥n> 1 的算法被稱作“指數(shù)時間算法”。

算法復(fù)雜度的分類有哪些?

算法復(fù)雜度分為時間復(fù)雜度和空間復(fù)雜度。其作用：時間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量;而空間復(fù)雜度是指執(zhí)行這個算法所需要的內(nèi)存空間。(算法的復(fù)雜性體運(yùn)行該算法時的計(jì)算機(jī)所需資源的多少上，計(jì)算機(jī)資源最重要的是時間和空間(即寄存器)資源，因此復(fù)雜度分為時間和空間復(fù)雜度。)

標(biāo)簽： 時間復(fù)雜度是什么意思 算法復(fù)雜度的分