衡量代碼的運(yùn)行效率對(duì)于工程師來說是一項(xiàng)非常重要的基本技能。
兩種復(fù)雜性概述
復(fù)雜度是衡量代碼運(yùn)行效率的重要衡量因素。 對(duì)于計(jì)算機(jī)來說，它是通過程序執(zhí)行計(jì)算任務(wù)的過程，即處理輸入數(shù)據(jù)并獲得最終結(jié)果。
編寫代碼的核心是完成計(jì)算。
對(duì)于同一個(gè)計(jì)算任務(wù)，使用不同的計(jì)算方法獲得結(jié)果的過程的復(fù)雜度是不同的。
例如：數(shù)據(jù)需要在在線系統(tǒng)中實(shí)時(shí)處理。 當(dāng)系統(tǒng)平均每分鐘添加300M數(shù)據(jù)，而我們的代碼在一分鐘內(nèi)無法完成這300M數(shù)據(jù)的處理時(shí)，系統(tǒng)就會(huì)出現(xiàn)異常。 首先，計(jì)算機(jī)執(zhí)行速度變得越來越慢效率是時(shí)間還是速度，直到系統(tǒng)死機(jī)。
當(dāng)出現(xiàn)這種問題時(shí)，我們首先要從降低代碼復(fù)雜度的角度來處理。 這時(shí)候我們就需要考慮代碼的時(shí)間復(fù)雜度和空間復(fù)雜度。
對(duì)于計(jì)算機(jī)程序來說效率是時(shí)間還是速度，其消耗的資源就是計(jì)算過程中所需的時(shí)間和空間。
當(dāng)然，程序的資源消耗不能用絕對(duì)的方式來衡量，因?yàn)闊o論是時(shí)間還是空間，它們消耗的資源都與輸入數(shù)據(jù)量密切相關(guān)。 準(zhǔn)確地說，它們是密切的、正相關(guān)的，也就是說，對(duì)于少量的數(shù)據(jù)，消耗的資源自然會(huì)更少。
為了更客觀地衡量消耗程度，我們通常關(guān)注時(shí)間或空間消耗與數(shù)據(jù)量之間的關(guān)系。
第二種復(fù)雜性的具體表現(xiàn)
根據(jù)復(fù)雜度的表達(dá)，復(fù)雜度可以理解為關(guān)于輸入數(shù)據(jù)量n的函數(shù)。 當(dāng)代碼的復(fù)雜度為f(n)時(shí)，我們可以使用大寫字母O和括號(hào)將復(fù)雜度表示為O(f(n))。
例如，O(n)表示復(fù)雜度與計(jì)算實(shí)例數(shù)n線性相關(guān)；
O(logn)表示復(fù)雜度與計(jì)算實(shí)例的數(shù)量n成對(duì)數(shù)關(guān)系。
四種復(fù)雜度計(jì)算原則
注：O(1)也代表一種特殊的復(fù)雜度，即可以用有限且可數(shù)的資源來完成某項(xiàng)任務(wù)。 這里有限可數(shù)的具體含義是它與輸入數(shù)據(jù)量n無關(guān)。
