算法基礎ppt課件(編輯修改稿)
2025-05-26 03:26 本頁面
【文章內容簡介】 f(n) ? 增長情況呢？ ? n擴大 10倍， f(n)擴大 100倍， g(n)也擴大 100倍 ? 兩個算法的增長情況一樣！ ? 漸進時間復雜度一樣！ 23 漸近性時間復雜度 ? f(n)=n2和 g(n)=n2/2 ? 增長情況一樣 ? 如何表示“增長情況”？ ? 把 f(n)和 g(n)變成“漸進”形式，然后直接比較 ? 如何變成“漸進”形式？ ? 只保留最“大”項 ? 忽略系數 ? 例 1： 3n4+8n2+n+2 ? n4 ? 例 2： 2n+1+n100+5 ? 2n (為什么 n+1變成了 n？ ) 24 復雜度分析不是萬能的 ? 回憶剛才的變換方法 ? 變換前后的增長情況一致 ? 需要先寫出完整的式子 ? 至少知道最大項 ? 可是很多情況下無法知道最大項 … ? 不信？ ? 一個數 n，如果它是奇數則變換到 3n+1，否則變換到 n/2 ? 給一個數 n，不停的變換下去，經過幾步變成 1？ ? 你知道它的運行時間嗎 ?! ? 這是個著名的停機問題 ? 復雜度分析不是萬能的！ 25 復雜度分析不清楚怎么辦 ? 只分析上限，而不管實際運行時間 ? 若 n充分大時 |f(n)|=c|g(n)|，其中 c為某常數 ? 記 f(n) = O(g(n))，表示 g(n)為 f(n)的漸進上限 ? 例 1： 5n2+3n+1 = O(n2) ? 例 2： 2n3 = O(7n8) ? 由于上限有無限多個，我們希望它盡量精確 ? 否則我們的分析就過于悲觀了，實際算法沒那么糟糕 ? 類似的，可以定義下限 Ω ? 如果上下限相等，那么增長情況就完全一樣了 ? 記做 Θ 26 復雜度的等級 ? 多項式算法 ? O(nt)， t是常數 ? O(logtn), t是常數 ? O(loglogn), 奇怪嗎？ ? 兩個多項式時間復雜度的積仍是多項式的 ? 排序 ? O(1) O(loglogn) O(logn) O(n1/2) O(n) ? O(n) O(nloglogn) O(nlogn) O(n2) ? O(n2) O(n3) O(2n) O(n!) O(nn) 27 復雜度曲線 1101001000100000 1 2 3 4 5 6 7 8 9 102^nn^2nlognnlogn28 不同情況的時間開銷 ? 輸入規(guī)模決定運行時間嗎？ for i := 1 to n do read(a[i])。 for i := 1 to n1 do if a[i] a[i+1] then do_it。 ? 假設 do_it操作為一次基本操作，忽略其他 ? 如果輸入是從小大到排序好的，則操作數為 0 ? 如果輸入是從大到小排序好的，則操作數為 n1 ? 即使規(guī)模 (n)相同，不同的輸入導致不同的運行時間！ 29 一道題目 ? 給一串整數 a[1…n] ，求出它和最大的子序列，即找出 1=i=j=n，使a[i]+a[i+1]+…+a[j] 最大 ? 介紹四個算法并分析時間復雜度 ? 枚舉： O(n3) ? 優(yōu)化的枚舉： O(n2) ? 分治： O(nlogn) ? 貪心： O(n) 30 算法一 ? 思想：枚舉所有的 i和 j，計算 a[i]+…+a[j] ，選擇最大的 ? 程序如下： max := a[1]。 for i:=1 to n do for j:=i to n do begin sum := 0。 for k:=i to j do sum := sum + a[k]。 if sum max then max := sum。 end。 End。 ? 時間復雜度如何分析？ 31 算法一分析 ? 當 i和 j一定的時候，內層循環(huán)執(zhí)行 ji+1次 ? 總次數為 ? 應該如何計算？ ? 方法一：直接計算 ? 先計算里層求和號，得 ? 再加起來？好復雜 … ? 自己做一做吧，得利用公式 12+…+n 2=O(n3) ? 一般地，有 1k+…+n k=O(nk+1) 1( 1
教學課件相關推薦
鄂ICP備17016276號-1