算法基礎ppt課件-資料下載頁
2025-04-29 03:26本頁面
【正文】 ? 和 O(n)在實際中相差并不是非常大 40 算法三分析（續(xù)三） ? 一般情形： T(n) = aT(n/b) + f(n) ? a, b為常數(shù)， f(n)為給定函數(shù) ? 遞歸樹得到的結果： ? 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項，有 2kf(n/2k) = 2k *n/2k = n ? 一共有 log2n項 ? T(n) = n * log2n = O(nlogn). n=100,000 ? 底數(shù) 2為什么沒有了呢？ ? 換底公式： logan/logbn=logba=常數(shù) 41 算法四 ? 算法二的實質是求出 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)新低，應該讓 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。 時間復雜度很明顯： O(n). n = 1,000,000 42 擴展 ? 給 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 總結 算法 時間復雜度 分析方法 枚舉 O(n3) 分層求和 優(yōu)化枚舉 O(n2) 明顯 分治 O(nlogn) 遞歸樹 掃描 O(n) 明顯 45 需要學會的東西 ? 為什么要分析算法 ? 算法分析的結果是什么樣子 ? 具體時間？ No ? 基本操作的次數(shù)？ Yes ? 漸進分析的結果：增長情況 ? 為什么分析增長情況？計算機速度彌補運行時間 ? O(n), O(nlogn), O(n2) … 分別能支持多大規(guī)模？ ? 分析簡單的代碼（幻燈片 8， 9， 10） ? 為什么要區(qū)分最壞、最好、平均情況 ? 算法都是可以分析的嗎？ ? 為什么要定義上限、下限 ? 難點一：靈活的應用漸進分析 ? 難點二：用遞歸樹解遞歸方程 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 習題 11：函數(shù)的漸進表達式 ? 求下列函數(shù)的漸進表達式 ? 3n2+10n ? n2/10+2n； ? 21＋ 1/n； ? logn3 ? 10 log3n ? 習題 O(1)和 O(2)的區(qū)別 49 按照漸進序排列下列表達式 ? 4n2, logn, 3n, 20n, 2, n2/3,n! 50 習題 1－ 2 算法效率 ? 假設某算法在輸入規(guī)模為 n時的計算時間為 T(n)＝ 3 2n。在某臺計算機上實現(xiàn)并完成該算法的時間為 t秒?，F(xiàn)有另一臺計算機，其運行速度是第一臺的 64倍，那么在這一臺機器上使用同一算法在 t秒內能夠解決輸入規(guī)模為多大的問題？ 51 ? 若算法效率改進為 T(n)＝ n2，那么能夠運行多大規(guī)模的問題？ ? 進一步改進為 T(n)＝ 8，那么其能夠運行多大規(guī)模的問題？
教學課件相關推薦
鄂ICP備17016276號-1