一.分析時(shí)間復(fù)雜度
首先，寫下推導(dǎo)大O階的方法：
1.用1取代運(yùn)行時(shí)間中的所有加法常數(shù)
2.只保留最高階項(xiàng)
3.去掉最高階項(xiàng)的系數(shù)，若有最高階項(xiàng)且不是1
1 ) 為何用“1”取代加法常數(shù)？
無論輸入數(shù)據(jù)增大多少倍，執(zhí)行的時(shí)間、消耗的空間與輸入數(shù)據(jù)大小無關(guān)。
則規(guī)定它的時(shí)間復(fù)雜度表示為O(1)，
不能以O(shè)(3)等其他數(shù)字來表示。
2 ) 分析時(shí)間復(fù)雜度時(shí)，為什么忽略常數(shù)項(xiàng)？為什么只保留最高次項(xiàng)？為什么要去掉最高次項(xiàng)系數(shù)？
為了讓自己加快進(jìn)度，就不以圖畫的方式表示了。
-
比如有三個(gè)算法： A（4n+8）； B（2n^2+10）；C （2n^2+9n+1）
1.在n<=3的時(shí)候，A算法的執(zhí)行次數(shù)要多于B
2.假設(shè)n很大時(shí)，比如1000：
A算法執(zhí)行4008次，B算法卻執(zhí)行了2000010次；
很明顯A的效率遠(yuǎn)好于算法B。并且去掉常數(shù)項(xiàng) 與 其最高項(xiàng)系數(shù)，也不會(huì)有明顯變化。所以，我們?cè)诜治鰰r(shí)間復(fù)雜度時(shí)，可以忽略常數(shù)項(xiàng) 與 最高次項(xiàng)系數(shù)。同理，算法B與算法C，在n=1,000,000時(shí)：
B執(zhí)行2 000 000 000 010次，C執(zhí)行200 000 9000 001次
可以說，隨著n的增大，算法B在趨近與算法C，
所以，判斷一個(gè)算法得效率時(shí)，要關(guān)注最高階項(xiàng)的階數(shù)，可以忽略掉函數(shù)中的常數(shù)項(xiàng)與次要項(xiàng)。
二.常見的時(shí)間復(fù)雜度
耗費(fèi)時(shí)間從多到少排列：
| 執(zhí)行次數(shù)函數(shù)舉例 | 階 | 非正式術(shù)語 |
|---|---|---|
| n! | O(n!) | 階乘階 |
| 2^n | O(2^n) | 指數(shù)階 |
| 6n^3 +2n^2+3n | O(n^3) | 立方階 |
| 3n^2+6 | O(n^2) | 平方階 |
| 2n+3n㏒(2)n | O(n㏒n) | n㏒n階 |
| 2n+1 | O(n) | 線性階 |
| 5㏒(2)n | O(㏒n) | 對(duì)數(shù)階 |
| 10 | O(1) | 常數(shù)階 |
自己在這里標(biāo)記一下O(logn)是如何分析的，我總是不會(huì)立馬反應(yīng)出相關(guān)情景：
- 比如有序數(shù)組{4,5,5,6,8,7,9,10}，使用二分法找到10(最壞的情況)：
1.第一次找到分量6，比10小，包括6和其左邊剩下的一半就不用再判斷了
2.這樣一半一半地去找，N折半后是N/2，再次是N/4……直到二分到N/N=1
3.進(jìn)而想出算式 N*（1/2）^x=1，x=log(2)N
4.log(2)8最多可以分割3次,即執(zhí)行3次
簡(jiǎn)單的的說，就是2^x = N，所以x=log2N
三.算法空間復(fù)雜度
1.通常，使用“空間復(fù)雜度”表示空間需求。使用“時(shí)間復(fù)雜度”表達(dá)時(shí)間的需求。
2.直接講“復(fù)雜度”，一般是指“時(shí)間復(fù)雜度”。
3.若輸入數(shù)據(jù)所占空間只取決于問題本身，與算法無關(guān)，一般所討論的是除正常占用內(nèi)存開銷外的輔助存儲(chǔ)單元規(guī)模。
4.若算法執(zhí)行時(shí)所需的輔助空間，相對(duì)于數(shù)據(jù)量來說是個(gè)常數(shù)，則空間復(fù)雜度為O(1)，稱為原地工作。
假設(shè)原始數(shù)據(jù)大小為n，一個(gè)算法需要m大小的內(nèi)存才能運(yùn)行，那么我們就有一個(gè)函數(shù)f(n)=m。
比如說，如果用冒泡排序?qū)?shù)據(jù)排序，如果直接在原始數(shù)據(jù)上排，那么根本不需要額外的存儲(chǔ)空間，而只需要定義幾個(gè)變量，那么復(fù)雜度就是1。
如果排序產(chǎn)生一個(gè)新的數(shù)組，不修改原來的數(shù)組，那么對(duì)于排序n個(gè)數(shù)據(jù)，就需要n個(gè)新的存儲(chǔ)空間，那么復(fù)雜度就是n。
再比如，對(duì)于兩個(gè)數(shù)組，求它們的笛卡兒積（比如a=1,2,3 b=a,b，結(jié)果是1a 1b 2a 2b 3a 3b），那么它的復(fù)雜度就是n^2
算法空間復(fù)雜度的計(jì)算公式：S（n） = O（f(n)）
n為問題的規(guī)模
f(n)為語句關(guān)于n所占存儲(chǔ)空間的函數(shù)
還需要注意:
1.遞歸算法的空間復(fù)雜度=遞歸深度N*每次遞歸所要的輔助空間
2.對(duì)于單線程來說，遞歸有運(yùn)行時(shí)堆棧，求的是遞歸最深的那一次壓棧所耗費(fèi)的空間的個(gè)數(shù)，因?yàn)檫f歸最深的那一次所耗費(fèi)的空間足以容納它所有遞歸過程。
四.算法的相關(guān)概念
1.算法的定義：算法是解決特定問題的求解步驟的描述。 在計(jì)算機(jī)中為指令的有限序列，并且每條指令表示一個(gè)或多個(gè)操作。
2.算法的特性：有窮性、確定性、可行性、輸入、輸出。
3.算法的設(shè)計(jì)要求：正確性、可讀性、健壯性、高效率和低存儲(chǔ)量需求。
4.算法的度量方法：事后統(tǒng)計(jì)方法（不科學(xué)，不準(zhǔn)確）、事前分析估算方法。
再舉例理解一個(gè)概念：漸進(jìn)增長(zhǎng)
判斷一個(gè)算法好不好，只通過少量的數(shù)據(jù)是不能做出準(zhǔn)確判斷的；我們可以比對(duì)算法的關(guān)鍵執(zhí)行次數(shù)函數(shù)的漸進(jìn)增長(zhǎng)性來判斷：
漸進(jìn)增長(zhǎng)的概念：
- 給定兩個(gè)函數(shù)F(n)與G(n)，如果存在一個(gè)整數(shù)num，使得所有的 n>num，且F(n)總比G(n)大，
那么函數(shù)F(n)的增長(zhǎng)漸進(jìn)快于G(n)通過比對(duì)算法的關(guān)鍵執(zhí)行次數(shù)函數(shù)漸進(jìn)增長(zhǎng)性，判斷某個(gè)算法A隨n的增大，會(huì)優(yōu)于算法B
假設(shè)有 算法A（2n^2） 算法B（3n+1）?？梢岳斫鉃?br> 算法A 要進(jìn)行兩次循環(huán)，3次賦值操作；
算法B 也類似地進(jìn)行 3n+1 次操作：
可以看出：
n=1時(shí)，算法B比A少操作一次
n=2時(shí)，二者的效率相同
之后隨n的增大，算法A的優(yōu)勢(shì)越來越明顯
- 并且可得出結(jié)論：n沒有限制的情況下，在n超過2后，算法B的漸進(jìn)增長(zhǎng)快于算法A。
