算法基礎(chǔ)ppt課件(參考版)
2025-05-02 03:26本頁面
【正文】 現(xiàn)有另一臺計算機(jī)，其運(yùn)行速度是第一臺的 64倍，那么在這一臺機(jī)器上使用同一算法在 t秒內(nèi)能夠解決輸入規(guī)模為多大的問題？ 51 ? 若算法效率改進(jìn)為 T(n)＝ n2，那么能夠運(yùn)行多大規(guī)模的問題？ ? 進(jìn)一步改進(jìn)為 T(n)＝ 8，那么其能夠運(yùn)行多大規(guī)模的問題？ 。 時間復(fù)雜度很明顯： O(n). n = 1,000,000 42 擴(kuò)展 ? 給 n*n矩陣，求和最大的子矩陣 43 分析 ? 枚舉起、止行號 r1和 r2，壓縮子矩形成為一行，變成一維問題 , 第 i個元素為 b[i] = a[r1,i]+a[r1+1,i]+…+a[r2,i] ? 對于第 i列 , 計算前綴和prefixi[j]=a[1,i]+a[2,i]+…+a[j,i] ? 則 b[i]=prefixi[r2]prefixi[r11], 常數(shù)時間 ? 計算前綴和 : O(n2), 一維問題 : O(n) ? 共 O(n3) 44 總結(jié) 算法 時間復(fù)雜度 分析方法 枚舉 O(n3) 分層求和 優(yōu)化枚舉 O(n2) 明顯 分治 O(nlogn) 遞歸樹 掃描 O(n) 明顯 45 需要學(xué)會的東西 ? 為什么要分析算法 ? 算法分析的結(jié)果是什么樣子 ? 具體時間？ No ? 基本操作的次數(shù)？ Yes ? 漸進(jìn)分析的結(jié)果：增長情況 ? 為什么分析增長情況？計算機(jī)速度彌補(bǔ)運(yùn)行時間 ? O(n), O(nlogn), O(n2) … 分別能支持多大規(guī)模？ ? 分析簡單的代碼（幻燈片 8， 9， 10） ? 為什么要區(qū)分最壞、最好、平均情況 ? 算法都是可以分析的嗎？ ? 為什么要定義上限、下限 ? 難點一：靈活的應(yīng)用漸進(jìn)分析 ? 難點二：用遞歸樹解遞歸方程 46 實驗一 (1) 3n+1 problem 47 實驗一（ 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時的計算時間為 T(n)＝ 3 2n。 if s[j] min_s then min_s := s[j]。 時間復(fù)雜度：預(yù)處理 +主程序 =O(n+n2)=O(n2). n=3000 35 算法三 ? 用一種完全不同的思路 ? 最大子序列的位置有三種可能 ? 完全處于序列的左半，即 j=n/2 ? 完全處于序列的右半，即 i=n/2 ? 跨越序列中間，即 in/2j ? 用遞歸的思路解決！ ? 設(shè) max(i, j)為序列 a[i…j] 的最大子序列 ? 那么 … 36 算法三（續(xù)） ? 用遞歸的思路解決！ ? 設(shè) max(i, j)為序列 a[i…j] 的最大子序列 ? 設(shè) mid = (i + j)/2，即區(qū)間 a[i…j] 的中點 ? 最大的第一種序列為 max(i, mid) ? 最大的第二種序列為 max(mid+1, j) ? 問題：最大的第三種序列為？？？ ? 既然跨越中點，把序列 a[i…j] 劃分為兩部分 ? a[i…mid] ：最大序列用掃描法在 n/2時間內(nèi)找到 ? 一共只有 mid1=n/2種可能的序列，一一比較即可 ? a[mid+1…j] ：同理 ? 一共花費(fèi)時間為 ji+1 37 算法三分析 ? 如何分析時間復(fù)雜度呢？ ? 我們沒有得到具體的 T(n)的式子 ? 只有一個遞推式子 T(n) = 2T(n/2) + n ? 設(shè)時間復(fù)雜度的精確式子是 T(n) ? 第一、二種序列的計算時間是 T(n/2)，因為序列長度縮小了一半 ? 第三種序列的計算時間是 n ? 計算出 T(n
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1