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