算法基礎(chǔ)ppt課件(存儲版)
【正文】 2： 5,4,3,2,1 yes 例 3： 3,2,4,5,1 yes；例 4： 3,1,4,5,2 no C A B 1 ,2 ,3 ,4 ,5 5 ,4 ,3 ,2 ,1 48 習(xí)題 11：函數(shù)的漸進(jìn)表達(dá)式 ? 求下列函數(shù)的漸進(jìn)表達(dá)式 ? 3n2+10n ? n2/10+2n； ? 21＋ 1/n； ? logn3 ? 10 log3n ? 習(xí)題 O(1)和 O(2)的區(qū)別 49 按照漸進(jìn)序排列下列表達(dá)式 ? 4n2, logn, 3n, 20n, 2, n2/3,n! 50 習(xí)題 1－ 2 算法效率 ? 假設(shè)某算法在輸入規(guī)模為 n時的計算時間為 T(n)＝ 3 2n。 if s[j] min_s then min_s := s[j]。 ? 時間復(fù)雜度如何分析？ 31 算法一分析 ? 當(dāng) i和 j一定的時候，內(nèi)層循環(huán)執(zhí)行 ji+1次 ? 總次數(shù)為 ? 應(yīng)該如何計算？ ? 方法一：直接計算 ? 先計算里層求和號，得 ? 再加起來？好復(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ìn)時間復(fù)雜度呢？ ? 何必非要計算出詳細(xì)的公式再化簡呢？ ? 里層求和計算出的結(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)計算出 s[1], …, s[n] s[0] := 0。 end ? 第 i次循環(huán)執(zhí)行了 i個操作 ? 總時間復(fù)雜度為 1+2+3+…+n = n(n+1)/2 22 比較兩個算法 ? 算法一執(zhí)行了 f(n)=n2次基本操作 ? 算法二執(zhí)行了 g(n)=n2/2次基本操作 ? 那個算法好呢？ ? 算法二好，因?yàn)?g(n) f(n) ? 增長情況呢？ ? n擴(kuò)大 10倍， f(n)擴(kuò)大 100倍， g(n)也擴(kuò)大 100倍 ? 兩個算法的增長情況一樣！ ? 漸進(jìn)時間復(fù)雜度一樣！ 23 漸近性時間復(fù)雜度 ? f(n)=n2和 g(n)=n2/2 ? 增長情況一樣 ? 如何表示“增長情況”？ ? 把 f(n)和 g(n)變成“漸進(jìn)”形式，然后直接比較 ? 如何變成“漸進(jìn)”形式？ ? 只保留最“大”項 ? 忽略系數(shù) ? 例 1： 3n4+8n2+n+2 ? n4 ? 例 2： 2n+1+n100+5 ? 2n (為什么 n+1變成了 n？ ) 24 復(fù)雜度分析不是萬能的 ? 回憶剛才的變換方法 ? 變換前后的增長情況一致 ? 需要先寫出完整的式子 ? 至少知道最大項 ? 可是很多情況下無法知道最大項 … ? 不信？ ? 一個數(shù) n，如果它是奇數(shù)則變換到 3n+1，否則變換到 n/2 ? 給一個數(shù) n，不停的變換下去，經(jīng)過幾步變成 1？ ? 你知道它的運(yùn)行時間嗎 ?! ? 這是個著名的停機(jī)問題 ? 復(fù)雜度分析不是萬能的！ 25 復(fù)雜度分析不清楚怎么辦 ? 只分析上限，而不管實(shí)際運(yùn)行時間 ? 若 n充分大時 |f(n)|=c|g(n)|，其中 c為某常數(shù) ? 記 f(n) = O(g(n))，表示 g(n)為 f(n)的漸進(jìn)上限 ? 例 1： 5n2+3n+1 = O(n2) ? 例 2： 2n3 = O(7n8) ? 由于上限有無限多個，我們希望它盡量精確 ? 否則我們的分析就過于悲觀了，實(shí)際算法沒那么糟糕 ? 類似的，可以定義
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1