今天分享的是時間復雜度沫勿、空間復雜度相關內(nèi)容，可以簡單了解下復雜度相關的知識味混。

復雜度：復雜度描述的是算法執(zhí)行時間或占用空間與數(shù)據(jù)規(guī)模的增長關系

我們用大O表示法來表達復雜度關系 T(n) = O(f(n))

其中 T(n) 是代碼的執(zhí)行時間产雹，n 表示數(shù)據(jù)的規(guī)模，f(n)表示代碼執(zhí)行的總次數(shù)翁锡。O 表示代碼的執(zhí)行時間 T(n) 與 f(n) 成正比關系蔓挖。要注意的是 大O時間復雜度表示的并不是代碼真正的執(zhí)行時間，而是表示代碼執(zhí)行時間隨數(shù)據(jù)規(guī)模增長的變化趨勢（大O復雜度分析法只是表示一種變化趨勢盗誊，通常忽略低階时甚，系數(shù)，常量哈踱，只需看最大階的量級）荒适，所以，也叫做時間漸進復雜度开镣，簡稱時間復雜度刀诬。

分析時間復雜度的三種方法：

1.?只關注循環(huán)代碼執(zhí)行次數(shù)最多的一段代碼

前面介紹到大O復雜度分析法只是表示一種變化趨勢，通常忽略低階邪财，系數(shù)陕壹，常量，只需看最大階的量級树埠。所以在分析代碼的時候糠馆，只關注循環(huán)次數(shù)最多的那一段代碼就好

分析：2,3行是常量級執(zhí)行時間，與n無關怎憋，對復雜度度沒啥影響又碌。4,5行是循環(huán)次數(shù)執(zhí)行最多的，這兩行代碼執(zhí)行了n次绊袋，所以時間復雜度是O(n)

1.?加法法則（量級最大法則）：總復雜度等于量級最大的那段代碼的復雜度

上面代碼主要是求sum_1,sum_2,sum_3毕匀，然后在求三者之和。

sum_1執(zhí)行100次癌别，是常量的執(zhí)行時間皂岔，和規(guī)模n無關。這里需要注意展姐，即使這段代碼執(zhí)行100000次或更多次躁垛，只要是一個已知的數(shù)剖毯，跟n無關，就是常量級的執(zhí)行時間教馆。當n無限大的時候速兔，可以忽略。盡管對代碼執(zhí)行時間有很大影響活玲，但時間復雜度表示的是一個算法執(zhí)行效率與數(shù)據(jù)規(guī)模增長的變化趨勢所以不管常量的執(zhí)行時間多大，都可以忽略谍婉。因為它本身對增長趨勢沒有影響舒憾。

同理，sum_2和sum_3分別是 O(n)和O(n^2)穗熬，對于這三個镀迂，我們?nèi)×考壸畲蟮腛(n^2)，所以總的時間復雜度就等于量級最大的那段代碼的時間復雜度唤蔗。

抽象一下：T1(n)=O(f(n)),T2(n)=O(g(n))探遵，T(n)=T1(n)+T2(n)=max(O(f(n)),O(g(n)))=O(max(f(n),g(n)))

3.乘法法則：嵌套代碼的復雜度等于嵌套內(nèi)外代碼復雜度的乘積

f()函數(shù)的時間復雜度是 T1(n)=O(n)，如果先把f()函數(shù)看成簡單的操作妓柜，則cal()函數(shù)的時間復雜度是T2(n)=O(n)箱季，所以整個cal()函數(shù)的時間復雜度是T(n)=T2(n)*T1(n)=O(n*n)=O(n^2)

①O(1)

O(1)是常量級時間復雜度的一種表示方法，并非只執(zhí)行一行代碼棍掐。只要代碼執(zhí)行時間不是隨著n的增大而增大藏雏，這樣的代碼的時間復雜度都是O(1)∽骰停或者說掘殴，通常只要算法中不存在循環(huán)、遞歸粟誓，即使代碼有很多行奏寨，時間復雜度仍是O(1)

上面的代碼是3行，但是時間復雜度是O(1)鹰服，而不是O(3)病瞳。

②O(logn)、O(nlogn)

對數(shù)階時間復雜度很常見获诈，同時也是很難分析的一種時間復雜度仍源。下面看一個例子

通過上面的分析時間復雜度的方法，我們可以知道這段代碼的第3行是執(zhí)行次數(shù)最多的舔涎，只要算出第3行執(zhí)行的次數(shù)笼踩，就是整個代碼的時間復雜度。 i從1開始取值亡嫌，每一次循環(huán)乘以2.可以看到 i=i*2是一個等比數(shù)列

我們只要算出x是多少嚎于，就是執(zhí)行的次數(shù)了? 2^x=n -->x=log2n掘而，所以時間復雜度應該為O(log2n)，如果代碼改下于购，時間復雜度是多少呢袍睡？

很容易就能看出來，應該是O(log3n)肋僧。

但是上面的O(log2n)和O(log3n)可以通過換底公式換成以2為底的對數(shù)斑胜，且可以忽略系數(shù)，所以都記做 O(logn)嫌吠。

關于O(nlogn),就是把上面的代碼在循環(huán)執(zhí)行n遍了止潘。其中歸并排序、快速排序的時間復雜度就是O(nlogn)

③O(m+n)辫诅、O(m*n)

這種類型的時間復雜度是由兩個參數(shù)決定的凭戴，先上例子

上面的代碼有m和n兩個數(shù)據(jù)規(guī)模，而且我們不能判斷兩個誰的量級大炕矮，所以不能簡單的用加法法則么夫，省略其中一個。那么這個例子的時間復雜度就是 O(m+n)

所以將加法法則做個修改：T1(m)+T2(n)=O(f(m)+g(n))

空間復雜度分析

前面說到時間復雜度全稱是漸進時間復雜度肤视，表示算法的執(zhí)行時間與數(shù)據(jù)規(guī)模之間的增長關系档痪。類比一下，空間復雜度全稱是漸進空間復雜度邢滑，表示算法的存儲空間與數(shù)據(jù)規(guī)模的增長關系钞它。

第2行代碼，申請了一個空間存儲變量i殊鞭，但它是常量階的遭垛，根數(shù)據(jù)規(guī)模n無關，可以忽略操灿。第3行申請了大小為n的int類型的數(shù)組锯仪，其余代碼則沒有申請空間。所以這段代碼的空間復雜度是 O(n)

常見的空間復雜度是 O(1)趾盐、O(n)庶喜、O(n^2)，對數(shù)階的復雜度平時用不到救鲤。

下面上一個復雜度趨勢圖

下面再來四個復雜度相關的知識點久窟，最好情況時間復雜度（best case time complexity）、最壞情況時間復雜度分析（worst case time complexity）本缠、平均情況時間復雜度（average case time complexity）斥扛、均攤時間復雜度（amortized time complexity）。

最好丹锹、最壞時間復雜度分析

上面代碼的功能是在一個數(shù)組中查找一個變量x出現(xiàn)的位置稀颁，如果沒有找到芬失，返回-1。這段代碼的時間復雜度應該為O(n)匾灶，其中n為數(shù)字的長度棱烂。

但是我們在數(shù)組中查找數(shù)據(jù)，并不需要每次都把數(shù)組都遍歷一遍阶女，因為有的數(shù)據(jù)在中途就找到颊糜，可以提前退出的，所以上面的代碼寫的不好秃踩，看下面的

我們發(fā)現(xiàn)芭析，在找到數(shù)據(jù)后，就退出了循環(huán)吞瞪。但是這個代碼的時間復雜度就不能簡單看成 O(n)了。因為我們沒有辦法判斷在哪個位置上找到這個元素驾孔，可能數(shù)組的第一個位置就是要找的數(shù)據(jù)芍秆，然后不需要遍歷后面的n-1個數(shù)據(jù)，那么時間復雜度是O(1)翠勉。如果數(shù)組中沒有找到這個元素妖啥，就需要把數(shù)組整個遍歷一遍，那么時間復雜度就是O(n)对碌。所以我們發(fā)現(xiàn)荆虱，不同情況，時間復雜度是不一樣的朽们。為了表示代碼在不同情況下的不同時間復雜度怀读，我們需要引入三個概念：最好情況時間復雜度、最壞情況時間復雜度和平均情況時間復雜度骑脱。同理菜枷，最壞情況時間復雜度就是，在最糟糕的情況下叁丧，執(zhí)行這段代碼的時間復雜度啤誊。像上面的例子中，如果要查找的元素沒有在數(shù)組中拥娄，就需要遍歷整個數(shù)組蚊锹。

平均情況時間復雜度最好情況時間復雜度和最壞情況時間復雜度都是在極端情況下的代碼的復雜度，發(fā)生的概率不大稚瘾。為了更好的表示平均情況下的復雜度牡昆，需要引入平均情況時間復雜度。還拿上面的例子舉例摊欠。要查找的元素在數(shù)組中的位置迁杨，有n+1種情況：在數(shù)組的0~n-1位置中和不在數(shù)組中钻心，共n+1種情況。把每種情況下铅协，查找需要遍歷的元素個數(shù)累加捷沸，然后除以 n+1，就能得到需要遍歷的元素的個數(shù)的平均值狐史。

因為大O表示法痒给，可以省略系數(shù)，所以平均情況時間復雜度為 O(n)骏全。但是這個計算過程是不嚴謹?shù)牟园兀驗樯厦娴膎+1種情況出現(xiàn)的概率并非都一樣。要查找的元素要么在數(shù)組中姜贡，要么不在數(shù)組中试吁，為了方便，假設在數(shù)組中和不在數(shù)組中的概率都為1/2楼咳。要查找的元素出現(xiàn)在 0~n-1個位置的概率也都是一樣的熄捍，為 1/n。所以要查找的元素出現(xiàn)在 0~n-1中任意位置的概率是 1/(2n)母怜。將上面的計算邏輯修改如下：

這個值就是概率論中的加權(quán)平均值余耽，也叫期望值，所以平均時間復雜度的全程應該叫加權(quán)平均時間復雜度或期望時間復雜度苹熏。我們發(fā)現(xiàn)碟贾，引入概率后，平均值為（3n+1）/4轨域。用大O表示法表示袱耽，去掉系數(shù)和常量，這段代碼的時間復雜度依然是 O(n)干发。其實扛邑，大多數(shù)情況，并不需要區(qū)分最好铐然、最壞蔬崩、平均情況時間復雜度。很多時候搀暑，用一個復雜度就可以滿足沥阳。只有同一個代碼在不同情況下，時間復雜度有量級的差距時自点，才引入這三個時間復雜度桐罕。

均攤時間復雜度

上面的代碼實現(xiàn)的是往數(shù)組中插入數(shù)據(jù)的功能。當數(shù)組滿了之后，用for循環(huán)遍歷數(shù)組求和功炮，并清空數(shù)組溅潜，將求和之后的sum值放到數(shù)組的第一個位置，然后再將新的數(shù)據(jù)插入薪伏。但如果數(shù)組一開始就有空閑空間滚澜，則直接將數(shù)據(jù)插入數(shù)組。分析這個代碼的時間復雜度嫁怀。最好的情況下设捐，數(shù)組中有空閑空間，直接將數(shù)據(jù)插入到數(shù)組下標為count的位置塘淑，所以最好情況時間復雜度是O(1)萝招。最壞的情況下，數(shù)組中沒有空閑空間了存捺，需要先遍歷數(shù)組求和槐沼，然后再將數(shù)組插入，所以最壞情況的時間復雜度是 O(n)捌治。平均時間復雜度分析如下：假設數(shù)組長度為n,根據(jù)數(shù)組插入的位置不同岗钩，分為n種情況，每種情況的時間復雜度為O(1)具滴。還有一種情況就是，數(shù)組沒有空閑空間了师倔，這個時候時間復雜度是O(n)构韵。這n+1種情況發(fā)生的概率相同，都是 1/(n+1)趋艘。所以平均時間復雜度為：

這個insert()和前面的find()是有區(qū)別的:

①find()在極端情況疲恢，復雜度才是O(1)。而insert()在大部分情況下都是O(1)瓷胧，只有個別情況才是O(n)

②insert()函數(shù)显拳，O(1)時間復雜度的插入和O(n)時間復雜度的插入，出現(xiàn)的頻率很有規(guī)律搓萧，并且有一定的前后時序關系杂数，一般都是一個O(n)插入后跟著n-1個O(1)插入，如此循環(huán)瘸洛。

所以針對insert()這種情況揍移，不需要像find()那樣根據(jù)概率計算平均時間復雜度。而是引入一種更加簡單的分析方法：攤還分析法反肋，通過攤還分析法得到的時間復雜度叫均攤時間復雜度那伐。

攤還分析法的使用：

還看insert()這個函數(shù)，每一次O(n)的插入，后面會跟著n-1次O(1)的插入操作罕邀，所以把耗時較多的那次操作均攤到接下來的n-1次耗時較少的操作上畅形，均攤下來，這一組連續(xù)的操作的均攤時間復雜度就是O(1)诉探。

攤還分析法的使用場景：

對于一個數(shù)據(jù)結(jié)構(gòu)進行一組連續(xù)的操作中日熬，大部分情況下時間復雜度都很低，只有個別情況下時間復雜度比較高阵具，而且這些操作之間存在前后連貫的時序關系碍遍，這個時候，就可以將這一組操作放在一起分析阳液，看是否能把較高時間復雜度的操作怕敬，平攤到其他不耗時的操作中。而且帘皿，在能夠應用均攤分析法的場景中东跪，一般均攤時間復雜度等于最好情況時間復雜度。

上面的分享希望大家好好看看鹰溜，對時間復雜度掃盲還是可以的

還是那句話虽填，“見識、目標曹动、認清差距斋日、努力+正確的方法”對人生成長無比重要，希望你通過此文有所啟發(fā)墓陈、收獲恶守！