散文網(wǎng) » 生活 »日常 » 時間復(fù)雜度&&空間復(fù)雜度

時間復(fù)雜度&&空間復(fù)雜度

2022-02-06 00:05 作者:hey_just_do_it 0人讀過 | 我要投稿

時間復(fù)雜度

常見的時間復(fù)雜度

時間復(fù)雜度是用來評估算法運行效率的單位，一般來說，時間復(fù)雜度高的算法比復(fù)雜度低的算法慢。之所以說一般來說符合情況是由于算法的數(shù)據(jù)規(guī)模一定程度上也影響著算法運行的快慢。常見的時間復(fù)雜度如下：

按效率對時間復(fù)雜度進行排序： $O(1)$ < $O(logn)$ < $O (n)$ < $O (n l o g n)$ < $O (n^{2})$ < $O (n^{2} l o g n) <$ O(n^3)...

快速判斷時間復(fù)雜度方法

在絕大多數(shù)簡單情況下，快速判斷復(fù)雜度的方法有：

確定數(shù)據(jù)規(guī)模n
如果循環(huán)在不斷減半，復(fù)雜度為 $l o g n$ (如常見時間復(fù)雜度中的最后一個例子)
如果是k層n的循環(huán)，復(fù)雜度為 $n^k$

空間復(fù)雜度

空間復(fù)雜度是用來評估算法內(nèi)存占用大小的單位?？臻g復(fù)雜度的表達方式與時間復(fù)雜度是完全一樣的，不過時間復(fù)雜度是根據(jù)算法語句的運行次數(shù)進行就計算的，而空間復(fù)雜度是根據(jù)算法運行過程中所占用的內(nèi)存空間進行計算的。以下為算法中幾個常見的簡單的空間復(fù)雜度：

如果算法只使用的幾個變量，則復(fù)雜度為 $O(1)$
如果算法使用了長度為n的一維列表，則復(fù)雜度為 $O(n)$
如果算法使用了m行n列的二維列表，則復(fù)雜度為 $O(m?n)$

一般情況下，我們可以使算法占用更多的內(nèi)存空間，以此來減小時間復(fù)雜度，即“空間換時間”。目前絕大多數(shù)公司更加關(guān)注算法的時間復(fù)雜度，因為它們一般都不缺內(nèi)存空間，愿意讓算法盡可能的占用更多內(nèi)存來減少算法的時間復(fù)雜度，從而提高用戶體驗感。

標簽：