如何設(shè)計(jì)一個高效的DSA呢揖庄？ 分而治之
不要一下解決 要分解問題成子問題 慢慢解決
舉一個很簡單的例子
時(shí)間復(fù)雜度是O(n) ?其實(shí)只需要看循環(huán)結(jié)構(gòu) ?沒有循環(huán)的地方復(fù)雜度肯定是O(1)
空間復(fù)雜度的兩種想法
1岩榆、輸入的A[] n 還有sum i
空間復(fù)雜度是O(n)
2系馆、輸入的A[] n 不計(jì)入 ?
只有sum i
我們更傾向于第二種
也就是這個算法的空間復(fù)雜度是O(1)
通常來講?
凡是空間復(fù)雜度的討論都是
除了輸入本身所占的空間之外
我們所需要的另加的用于計(jì)算所必須的空間
上述例子給了我們一個處理問題的方法
處理問題的方法：
這個平凡 指的是這個問題很容易解決了
縮減 指的是問題的規(guī)模小了 但是類型沒變?
因此可以一直這么處理下去 ?直到該大問題全部解決
遞歸算法分析的第一個技巧 遞歸跟蹤
遞歸跟蹤：
查看復(fù)雜度的時(shí)候 ?遞歸中調(diào)用自己的那個歸入下一層遞歸中 這一步的復(fù)雜度是O(1)不影響大局
當(dāng)前遞歸只關(guān)心A[n-1]這一步
可以看到的是每一步的sum(A,n)時(shí)間復(fù)雜度都是O(1)因?yàn)橹挥袀€加法
一共有n+1次遞歸 ?那么一共就有O(1)*（n+1）=O(n)
上述的遞歸是一個前遞歸產(chǎn)生一個后遞歸 ?也叫線性遞歸
為了更好的分析復(fù)雜的遞歸
我們給出另外一種方法 遞推方程
間接抽象,更適用于復(fù)雜的遞歸模式
如果遞歸
上述是隱式表達(dá) 由遞推方程和邊界條件就能解出顯式表達(dá)
另外一個例子：
另一個策略 分而治之
所謂的遞歸基 就是最簡單的情況 ?最容易解決的情況
就像下面的區(qū)間變成一個元素 區(qū)間上限下限相等
?這就是遞歸基
直到lo全部等于hi的時(shí)候才行
查看剛才的遞歸?
把遞歸調(diào)用本身去掉的話
沒有循環(huán) 也不包含任何隱式顯式迭代
所以要計(jì)算時(shí)間復(fù)雜度的話我們只需要把遞歸的個數(shù)算出來就行了
那么問題來了 ?：怎么算
從代數(shù)層面看 是列代數(shù)方程式
但是 我們不想 或者說 不喜歡你采用這種方式
我們從幾何層面看
每一層都是2的倍數(shù)對吧?
關(guān)鍵是最后一層是多少
最后一層是n 沒錯 為什么呢 ?因?yàn)樽詈笠恍械葍r(jià)于把每個元素羅列出來
最后一個元素其實(shí)就是n ?但是為了寫成 等比數(shù)列的形式呃展运。。蒂窒。也就是以2為倍數(shù)的幾何級數(shù)的形式
幾何級數(shù)的形式 時(shí)間復(fù)雜度與末項(xiàng)同階
再從遞歸方程的角度分析
MAX2問題?
首先第一個方法
最好和最壞情況比較次數(shù)都一樣都是2n-3
第二個方法 ?掃描一遍逐個比較
這個方法的好處在于 ?最好情況確實(shí)減少了時(shí)間 但是最壞情況并沒有改善
以上兩種情況都是只看了if語句 ?沒有關(guān)心里面的時(shí)間復(fù)雜度 或者說默認(rèn)了swap這個函數(shù)的復(fù)雜度是O(1)
以上算法的最壞情況沒有真正改進(jìn) ?接下來給出真正意義上的改進(jìn)算法
首先把整個數(shù)組劃為兩部分 ?然后分別求出這兩部分的最大值和次大值
X1L與X1R先比較 ?X1L勝出的話 ?X1L為整體最大值
X2L再和X1R比較 ?確定整體次大值
注意 這里X2R是不需要比較的
注意代碼語法 應(yīng)該是使用了引用的那個語法 &x1直接在函數(shù)里修改X1L X1R X2L X2R
自己寫一寫試試吧
