算法基礎(chǔ)ppt課件-文庫吧資料
2025-05-05 03:26本頁面
【正文】 )，就得到了時間復(fù)雜度 ? 怎樣計(jì)算 T(n)呢？ 38 遞歸樹分析 ? 一般情形： T(n) = aT(n/b) + f(n) ? a, b為常數(shù)， f(n)為給定函數(shù) ? 由遞歸樹得結(jié)果為 T(n) = f(n)+af(n/b)+a2f(n/b2)+…+a Lf(n/bL) ? 其中最后一項(xiàng)為遞歸邊界，即 n/bL=1，因此 L=logbn 39 算法三分析（續(xù)二） ? n/bL=1 ? 因此 bL=n ? 記 L = logbn，稱 L為以 b為底的 n的對數(shù) ? 對數(shù)的公式： ? logan + logam = loganm ? klogan = logank ? 換底公式： logan/logbn=logba ? 對數(shù)是一種增長很慢的函數(shù) ? log21000 約為 10 ? log21000000 約為 20 ? 時間復(fù)雜度 O(nlogn)和 O(n2)相比是很大的提高！ ? 和 O(n)在實(shí)際中相差并不是非常大 40 算法三分析（續(xù)三） ? 一般情形： T(n) = aT(n/b) + f(n) ? a, b為常數(shù)， f(n)為給定函數(shù) ? 遞歸樹得到的結(jié)果： ? T(n) = f(n)+af(n/b)+a2f(n/b2)+…+a Lf(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). n=100,000 ? 底數(shù) 2為什么沒有了呢？ ? 換底公式： logan/logbn=logba=常數(shù) 41 算法四 ? 算法二的實(shí)質(zhì)是求出 i=j,讓 s[j]s[i1]最大 ? 對于給定的 j，能否直接找到在 j之前的最小 s值呢？ ? 從小到大掃描 j ? j=1時，只有一個合法的 i，即 i=1, s[11]=0 ? 如果 s[j]變大，則最小的 s值和上次一樣 ? 如果 s[j]再創(chuàng)新低，應(yīng)該讓 s[j]作為今后的最優(yōu) s值 min_s := 0。 end。 34 算法二（續(xù)） ? 有了 s[i]，怎么快速求 a[i]+…+a[j] 呢？ a[i]+…+a[j] = (a[1] + … + a[j]) – (a[1] + … + a[i 1]) =s[j] – s[i1] 而 s[i]經(jīng)過預(yù)處理以后可以直接讀出！ ? 程序如下： max := a[1]。 ? 時間復(fù)雜度如何分析？ 31 算法一分析 ? 當(dāng) i和 j一定的時候，內(nèi)層循環(huán)執(zhí)行 ji+1次 ? 總次數(shù)為 ? 應(yīng)該如何計(jì)算？ ? 方法一：直接計(jì)算 ? 先計(jì)算里層求和號，得 ? 再加起來？好復(fù)雜 … ? 自己做一做吧，得利用公式 12+…+n 2=O(n3) ? 一般地，有 1k+…+n k=O(nk+1) 1( 1 )nni j iji??????11 ( 1 ) ( 2 )2nin i n i?? ? ? ??32 算法一分析（續(xù)） ? 總次數(shù)為： ? 完全的計(jì)算太麻煩 ? 能不能不動筆就知道漸進(jìn)時間復(fù)雜度呢？ ? 何必非要計(jì)算出詳細(xì)的公式再化簡呢？ ? 里層求和計(jì)算出的結(jié)果是 O((ni)2) ? 12+22+…+n 2=O(n3) ? 每步都化簡！但是要保留外層需要的變量 ? 結(jié)論：算法一時間復(fù)雜度為 O(n3) ? 經(jīng)驗(yàn)：一般只能支持 n=200 1( 1 )nni j iji??????33 算法二 ? 思路 ? 枚舉 i和 j后，能否快速算出 a[i]+…+a[j] 呢？ ? 預(yù)處理！ ? 記 s[i] = a[1] + a[2] + … + a[i], 規(guī)定 s[0] = 0 ? 則可以在 O(n)的時間內(nèi)計(jì)算出 s[1], …, s[n] s[0] := 0。 end。 for k:=i to j do sum := sum + a[k]。 ? 假設(shè) do_it操作
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1