11-編程的靈魂——數據結構算法=程序(編輯修改稿)
2024-08-31 07:28 本頁面
【文章內容簡介】 ? 由于上限有無限多個，我們希望它盡量精確 , 否則我們的分析就過于悲觀了，實際算法沒那么糟糕 五、遞歸式的遞歸樹分析 遞歸式 ? 在很多時候 , 無法寫出時間復雜度 T(n)的顯式表達式 , 而只能得到遞歸方程 – 公式一 : T(1)=1, T(n)=T(n1)+n, 則 T(n)為 n(n+1)/2 – 公式二 : T(1)=1, T(n)=T(n/2)+1, 則 T(n)約為 lgN – 公式三 : T(1)=0, T(n)=T(n/2)+n, 則 T(n)約為 2n – 公式四 : T(1)=0, T(n)=2T(n/2)+n, 則 T(n)約為 nlgN – 公式五 : T(1)=1, T(n)=2T(n/2)+1, 則 T(n)約為 2n ? 考慮一般情形 : T(n) = aT(n/b) + f(n) 遞歸樹分析 ? T(n) = aT(n/b) + f(n), a, b為常數， f(n)為給定函數 ? 遞歸樹 : T(n) = f(n)+af(n/b)+a2f(n/b2)+…+ aLf(n/bL) ? 其中最后一項為遞歸邊界，即 n/bL=1，因此 L=logbn 公式四分析 ? T(n) = aT(n/b) + f(n) ? 遞歸樹得到的結果： – T(n) = f(n)+af(n/b)+a2f(n/b2)+…+ aLf(n/bL) –其中 L=logbn ? 公式四： T(n) = 2T(n/2) + n – a = 2, b = 2, f(n) = n –對于第 k項，有 2kf(n/2k) = 2k *n/2k = n –一共有 log2n項 – T(n) = n * log2n = O(nlogn) 小結 ? 基本概念 –時空開銷，增長，漸進復雜度 –基本操作， 輸入規(guī)模、偽多項式算法、多項式算法（有效算法） ? 常用符號 – O（上限）、 Ω（下限）、 Θ（相同）； – o（松的） ? 時間復雜度和運行時間的關系 小結 ? 分析對象 –不同輸入的運行時間：最壞、最好、平均 –一定概率假設下的運行時間：期望 –不同效率的多個操作：平攤 ? 時空辨證關系 –時間換空間：重復計算 –空間換時間：預處理 六、算法設計與分析實例 最大連續(xù)序列問題 ? 給一串整數 a[1… n]，求出它和最大的子序列，即找出 1=i=j=n，使a[i]+a[i+1]+…+ a[j]最大 ? 介紹四個算法并分析時間復雜度 –枚舉： O(n3) –優(yōu)化的枚舉： O(n2) –分治： O(nlogn) –貪心： O(n) 算法一 max := a[1]。 for i:=1 to n do for j:=i to n do begin sum := 0。 for k:=i to j do sum := sum + a[k]。 if sum max then max := sum。 end。 ? 思想：枚舉所有的 i和 j，計算 a[i]+…+ a[j]，選擇最大的 ? 時間復雜度如何分析？ – 三層循環(huán) – 內層操作次數取決于 i, j – 中層操作次數取決于 i 算法一分析 ? 當 i和 j一定的時候，內層循環(huán)執(zhí)行 ji+1次 ? 總次數為 ? 應該如何計算？ ? 方法一：直接計算 – 先計算里層求和號，得 – 再加起來？好復雜 … – 直接算法需要利用公式 12+…+ n2=O(n3) – 一般地，有 1k+…+ nk=O(nk+1). 證明 : 數學歸納法 1( 1 )nni j iji??????11 ( 1 ) ( 2 )2nin i n i?? ? ? ??算法一分析（續(xù)） ? 總次數為： – 完全的計算太麻煩 – 能不能不動筆就知道漸進時間復雜度呢？ ? 何必非要計算出詳細的公式再化簡呢？ – 里層求和計算出的結果是 O((ni)2) – 12+22+…+ n2=O(n3) – 每步都化簡！但是要保留外層需要的變量 ? 結論：算法一時間復雜度為 O(n3) ? 經驗：一般只能支持 n=200 1( 1 )nni j iji??????算法二 ? 思 路 –枚舉 i和 j后，能否快速算出 a[i]+…+ a[j]呢？ –預處理！ –記 s[i] = a[1] + a[2] + … + a[i], 規(guī)定 s[0] = 0 –則可以在 O(n)的時間內計算出 s[1], …, s[n] s[0] := 0。 for i:=1 to n do s[i] := s[i–1] + a[i]。 算法二（續(xù)） ? 有了 s[i]，怎么快速求 a[i]+…+ a[j]呢？ a[i]+…+ a[j] = (a[1] + … + a[j]) – (a[1] + … + a[i1]) =s[j] – s[i1] 而 s[i]經過預處理以后可以直接讀出！ max := a[1]。 for i:=1 to n do for j:=i to n do if s[j] – s[i1] max then max := s[j] –
畢業(yè)設計相關推薦
鄂ICP備17016276號-1