算法基礎(chǔ)ppt課件-資料下載頁
2025-04-29 03:26本頁面
【正文】 ? 和 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 ? 對(duì)于第 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]最大 ? 對(duì)于給定的 j，能否直接找到在 j之前的最小 s值呢？ ? 從小到大掃描 j ? j=1時(shí)，只有一個(gè)合法的 i，即 i=1, s[11]=0 ? 如果 s[j]變大，則最小的 s值和上次一樣 ? 如果 s[j]再創(chuàng)新低，應(yīng)該讓 s[j]作為今后的最優(yōu) s值 min_s := 0。 for j :=1 to n do begin if s[j] – min_s max then max := s[j] – min_s。 if s[j] min_s then min_s := s[j]。 end。 時(shí)間復(fù)雜度很明顯： O(n). n = 1,000,000 42 擴(kuò)展 ? 給 n*n矩陣，求和最大的子矩陣 43 分析 ? 枚舉起、止行號(hào) r1和 r2，壓縮子矩形成為一行，變成一維問題 , 第 i個(gè)元素為 b[i] = a[r1,i]+a[r1+1,i]+…+a[r2,i] ? 對(duì)于第 i列 , 計(jì)算前綴和prefixi[j]=a[1,i]+a[2,i]+…+a[j,i] ? 則 b[i]=prefixi[r2]prefixi[r11], 常數(shù)時(shí)間 ? 計(jì)算前綴和 : O(n2), 一維問題 : O(n) ? 共 O(n3) 44 總結(jié) 算法 時(shí)間復(fù)雜度 分析方法 枚舉 O(n3) 分層求和 優(yōu)化枚舉 O(n2) 明顯 分治 O(nlogn) 遞歸樹 掃描 O(n) 明顯 45 需要學(xué)會(huì)的東西 ? 為什么要分析算法 ? 算法分析的結(jié)果是什么樣子 ? 具體時(shí)間？ No ? 基本操作的次數(shù)？ Yes ? 漸進(jìn)分析的結(jié)果：增長(zhǎng)情況 ? 為什么分析增長(zhǎng)情況？計(jì)算機(jī)速度彌補(bǔ)運(yùn)行時(shí)間 ? O(n), O(nlogn), O(n2) … 分別能支持多大規(guī)模？ ? 分析簡(jiǎn)單的代碼（幻燈片 8， 9， 10） ? 為什么要區(qū)分最壞、最好、平均情況 ? 算法都是可以分析的嗎？ ? 為什么要定義上限、下限 ? 難點(diǎn)一：靈活的應(yīng)用漸進(jìn)分析 ? 難點(diǎn)二：用遞歸樹解遞歸方程 46 實(shí)驗(yàn)一 (1) 3n+1 problem 47 實(shí)驗(yàn)一（ 2）鐵軌問題 例 1： 1,2,3,4,5 yes；例 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時(shí)的計(jì)算時(shí)間為 T(n)＝ 3 2n。在某臺(tái)計(jì)算機(jī)上實(shí)現(xiàn)并完成該算法的時(shí)間為 t秒?，F(xiàn)有另一臺(tái)計(jì)算機(jī)，其運(yùn)行速度是第一臺(tái)的 64倍，那么在這一臺(tái)機(jī)器上使用同一算法在 t秒內(nèi)能夠解決輸入規(guī)模為多大的問題？ 51 ? 若算法效率改進(jìn)為 T(n)＝ n2，那么能夠運(yùn)行多大規(guī)模的問題？ ? 進(jìn)一步改進(jìn)為 T(n)＝ 8，那么其能夠運(yùn)行多大規(guī)模的問題？
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1