case：斐波那契數(shù)列

　　　　　　1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144，...

　　　　　　線性遞推數(shù)列

 單位階躍函數(shù)如下：

代碼1：

1 int FIB(n){
2 
3 　　if n <= 1
4 
5 　　　　return 1;
6 　　else
7 
8 　　　　return FIB(n - 1) + FIB(n - 2);
9 }

問(wèn)題剖析： 

　　當(dāng)n > 1, 比如2的時(shí)候， FIB(0) 會(huì)被調(diào)用兩次。如果是更大的值，必然會(huì)出現(xiàn)一個(gè)結(jié)果重復(fù)調(diào)用的工作。如下圖：

時(shí)間復(fù)雜度為：T(n) = Θ(?^n)，是以的指數(shù)增長(zhǎng)，這個(gè)過(guò)程用來(lái)計(jì)算斐波那契數(shù)列是個(gè)相當(dāng)慢的方法。——得出結(jié)論：低效的方法。

 代碼2（升級(jí)版）：采用動(dòng)態(tài)多線程來(lái)重寫FIB過(guò)程，利用代碼1中FIB(n-1)和FIB(n-2)彼此獨(dú)立的特點(diǎn)，可以采用并行計(jì)算的方式升級(jí)過(guò)程。

int P-FIB(n)
    if n <= 1
        return n;
    else
        int x = spawn P-FIB(n - 1)
        int y = P-FIB(n - 2)
        sync
        return x + y

 關(guān)鍵字spawn的作用：嵌套并行調(diào)用。父進(jìn)程派生子進(jìn)程，與P-FIB(n - 2)并行執(zhí)行。

 關(guān)鍵字sync作用：同步語(yǔ)句。執(zhí)行完sync之后，一個(gè)過(guò)程（父進(jìn)程）才能安全地使用其派生子過(guò)程（子進(jìn)程）的返回值。sync表明，過(guò)程在執(zhí)行sync后面的語(yǔ)句前，必須等到它的所有派生子過(guò)程計(jì)算完成。

分析：

時(shí)間復(fù)雜度由代碼1的 T(n) = T(n-1) + T(n-2) 升級(jí)為T(n) = max(T(n-1), T(n-2)) ;

這里我們要理解一個(gè)重要的圖分析：有向無(wú)環(huán)圖

 公式：G=（V，E)

 ——V，代表定點(diǎn)（指令）；

 ——Ε ，代表邊（指令間的依賴關(guān)系）；

　　----如：(μ, ν) ∈  Ε 表示指令 μ必須在 ν之前執(zhí)行。