時(shí)間復(fù)雜度
1.時(shí)間復(fù)雜度，表示形式為?Big O notation?
????時(shí)間復(fù)雜度也可以理解為指令執(zhí)行多少次垮刹。好的時(shí)間復(fù)雜度程序届腐，會(huì)讓程序跑起來(lái)更快更節(jié)約資源昵观。從所有可能的解決方法中找出 時(shí)間最快、內(nèi)存最少?的最優(yōu)解決方法愉老。
2.常見(jiàn)的幾種時(shí)間復(fù)雜度
????O表示它的復(fù)雜度是n的怎樣的一個(gè)函數(shù)
? ? O(1)：Constant Complexity 常數(shù)復(fù)雜度
? ??O(log n)：Logarithmic Complexity 對(duì)數(shù)復(fù)雜度
? ??O(n)：Linear Complexity 線性時(shí)間復(fù)雜度
? ??O(n^2)：N square Complexity 平方
????O(n^3)：N cubic Complexity 立方
? ??O(2^n)：Exponential Complexity 指數(shù)
? ??O(n!)：Factorial 階乘
3.遞歸 時(shí)間復(fù)雜度分析
遞歸俺夕，關(guān)鍵是了解它的遞歸總共執(zhí)行了語(yǔ)句多少次裳凸。循環(huán)，比較好理解劝贸，n次循環(huán)就執(zhí)行了n次語(yǔ)句姨谷。遞歸是層層嵌套的，通秤尘牛可以把它的執(zhí)行順序畫出一個(gè)樹(shù)形結(jié)構(gòu)梦湘。
兩個(gè)現(xiàn)象：
1.每多展開(kāi)一層，運(yùn)行的節(jié)點(diǎn)數(shù)就是上面一層的2倍件甥。第一層1個(gè)節(jié)點(diǎn)捌议，第二層2個(gè)節(jié)點(diǎn)，第三層4個(gè)節(jié)點(diǎn)引有，第四層8個(gè)節(jié)點(diǎn)........以此類推瓣颅，它每一層的節(jié)點(diǎn)數(shù)即它的執(zhí)行次數(shù) 是按指數(shù)級(jí)遞增的。由此可見(jiàn)譬正，當(dāng)?shù)阶詈笠粚拥脑捁梗瑫?huì)變成2的n次方，大概這么一個(gè)數(shù)量級(jí)的節(jié)點(diǎn)曾我。那么可以肯定粉怕，最后總的執(zhí)行次數(shù)，就是變成指數(shù)級(jí)了抒巢。
2.有重復(fù)的節(jié)點(diǎn)出現(xiàn)在執(zhí)行狀態(tài)數(shù)中贫贝。F1、F2蛉谜、F3都被重復(fù)計(jì)算很多次稚晚，這些大量冗余的計(jì)算凤优，導(dǎo)致求第6個(gè)數(shù)的Fibonacci數(shù)變成了2的6次方這么一個(gè)繁復(fù)的時(shí)間復(fù)雜度。面試中不要這么寫算法蜈彼，可以加緩存筑辨，把中間節(jié)點(diǎn)的結(jié)果緩存下來(lái)，或者直接用循環(huán)來(lái)寫求和幸逆。
主定理
主定理：解決所有遞歸函數(shù)怎么計(jì)算時(shí)間復(fù)雜度
1》二分查找：有序數(shù)列棍辕，一分為二，只在一邊進(jìn)行查找还绘，O(log n)楚昭。
2》二叉樹(shù)遍歷：每次一分為二，但每一邊是相等的時(shí)間復(fù)雜度這么下去拍顷。簡(jiǎn)化思維：二叉樹(shù)遍歷每個(gè)節(jié)點(diǎn)都會(huì)訪問(wèn)一次抚太，且僅訪問(wèn)一次，O(n)昔案。
3》有序的二維矩陣：如果是一維的數(shù)組進(jìn)行二分查找為O(log n)尿贫，有序的二維矩陣二分查找時(shí)，被降了一維就不是n平方的算法踏揣，而是O(n)庆亡。
4》歸并排序
空間復(fù)雜度
兩條原則：
1.如果代碼里開(kāi)了數(shù)組，那么數(shù)組的長(zhǎng)度基本上就是你的空間復(fù)雜度捞稿。譬如長(zhǎng)度為n的一維數(shù)據(jù)又谋，空間復(fù)雜度為O(n)。長(zhǎng)度為n平方的二維數(shù)組娱局，空間復(fù)雜度為O(n^2)彰亥。
2.如果有遞歸的話，遞歸的深度就是就是你的空間復(fù)雜度的最大值衰齐。如果又有數(shù)組又有遞歸任斋，那兩者之間的最大值就是你的空間復(fù)雜度。
算法分析題解答：爬樓梯
