1. 算法的復(fù)雜度：
- 算法的復(fù)雜度分為時(shí)間復(fù)雜度和空間復(fù)雜度谭贪。
- 時(shí)間復(fù)雜度境钟，是衡量算法執(zhí)行時(shí)間的長(zhǎng)度；
- 空間復(fù)雜度俭识，是衡量算法存儲(chǔ)空間的大锌鳌；
2. 時(shí)間復(fù)雜度
時(shí)間頻度： 一個(gè)算法中語句執(zhí)行次數(shù)套媚，記為T（n）缚态；
-
時(shí)間復(fù)雜度：描述T（n）的變化規(guī)律，記作：T（n）=O(f(n));
- 大O記法：用來體現(xiàn)算法復(fù)雜度的標(biāo)記堤瘤。一般情況下玫芦，隨著n的增大，T（n）增長(zhǎng)最慢的稱為最優(yōu)算法本辐。
- 時(shí)間頻度不同桥帆，但時(shí)間復(fù)雜度可能相同。如：T(n)=n2+3n+4與T(n)=4n2+2n+1它們的頻度不同慎皱，但時(shí)間復(fù)雜度相同老虫，都為O(n2)。
-
推導(dǎo)大O階：
- 用常數(shù)1取代運(yùn)行時(shí)間中所有的加法常數(shù)茫多，如O（1）
- 在修改后的運(yùn)行次數(shù)憨厚祈匙，只保留最高階數(shù)，如n2+n為O(n2)
- 如果最高階數(shù)存在且不是1天揖，則去除與這個(gè)項(xiàng)相乘的常數(shù)夺欲，如3n3為O(n3)
-
常見時(shí)間復(fù)雜度：
-
常數(shù)階
常數(shù)階 -
線性階
線性階 -
對(duì)數(shù)階
對(duì)數(shù)階 -
平方階
平方階 -
對(duì)比圖
對(duì)比圖 -
常用時(shí)間復(fù)雜度大小
常用時(shí)間復(fù)雜度大小關(guān)系
-
最壞時(shí)間復(fù)雜度：
最壞情況下的時(shí)間復(fù)雜度稱最壞時(shí)間復(fù)雜度。一般不特別說明宝剖，討論的時(shí)間復(fù)雜度均是最壞情況下的時(shí)間復(fù)雜度洁闰。 這樣做的原因是：最壞情況下的時(shí)間復(fù)雜度是算法在任何輸入實(shí)例上運(yùn)行時(shí)間的上界，這就保證了算法的運(yùn)行時(shí)間不會(huì)比任何更長(zhǎng)万细。
3. 空間復(fù)雜度
算法的空間復(fù)雜度通過計(jì)算算法所需的存儲(chǔ)空間實(shí)現(xiàn)扑眉，算法的空間復(fù)雜度的計(jì)算公式為： S(n) = O(f(n))。
通常沒有特別指明時(shí)赖钞，復(fù)雜度指的是時(shí)間復(fù)雜度腰素，我們寫代碼時(shí)，要學(xué)會(huì)以空間來換取時(shí)間雪营。
