? ? ? ?正如前文所說(shuō)，我們把爬上N個(gè)臺(tái)階共有有多少種方法這一問(wèn)題通過(guò)遞歸的方法得以了解決，但問(wèn)題雖然解決了可我們想過(guò)這個(gè)程序的時(shí)空復(fù)雜度沒(méi)有？

? ? ? ? 首先，時(shí)間復(fù)雜度。它的時(shí)間復(fù)雜度是O(2^n)，隨著樓梯臺(tái)階數(shù)的增長(zhǎng)程序的運(yùn)行時(shí)間呈指數(shù)增長(zhǎng)。這是一種我們最不想看到的情況。再次，空間復(fù)雜度。由于采取函數(shù)的嵌套調(diào)用，程序運(yùn)行所需空間也是相當(dāng)大的。最后，那到底有沒(méi)有更好的優(yōu)化方法呢？

? ? ? ?答案是肯定的！如果大家把該問(wèn)題從頂而下的展開(kāi)來(lái)，應(yīng)該能發(fā)現(xiàn)它的所有求解函數(shù)F(X),X€{N,N-1,...,1}展開(kāi)式是以完全二叉樹(shù)的形式組織起來(lái)的，且相鄰節(jié)點(diǎn)的左右子樹(shù)的值相同，這意味著在求解過(guò)程中存在重復(fù)的內(nèi)容。

相同顏色的為重復(fù)的計(jì)算

? ? ? ? 所以我們可以通過(guò)一個(gè)哈希表存儲(chǔ)每一個(gè)求解函數(shù)的值，每當(dāng)求解一個(gè)F(X)的時(shí)候先從哈希表中查看有無(wú)該函數(shù)值，如果有現(xiàn)成的值，則直接返回結(jié)果，如果沒(méi)有就計(jì)算該值并把結(jié)果存入哈希表中。

圖片發(fā)自簡(jiǎn)書(shū)App

? ? ? ? 聽(tīng)著好復(fù)雜哦，那還有沒(méi)有更簡(jiǎn)單的辦法？答案也是肯定的?。?！那就是?自底向上。那么何為自底向上？如果仔細(xì)觀(guān)察，我們會(huì)發(fā)現(xiàn)，F(xiàn)(3)的值只取決于F(1)和F(2)，F(xiàn)(4)的值只取決于F(3)和F(2)，...，F(xiàn)(N)的值只取決于F(N-1)和F(N-2)。好了有了這個(gè)結(jié)論，我們就可以"撿西瓜丟芝麻"了，而不是像哈希表一樣，存儲(chǔ)所有計(jì)算過(guò)的F(X)，這樣是不是就大大大大減少了程序的空間復(fù)雜度？

圖片發(fā)自簡(jiǎn)書(shū)App

更多精彩內(nèi)容請(qǐng)關(guān)注?leon_Geo