cy分治解題報(bào)告ppt課件(編輯修改稿)
2025-01-04 02:42 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 元素分成大小大致相同的兩個(gè)子序列，分別對(duì) 2個(gè)子序列求逆序?qū)?shù)，再將 2個(gè)子序列合并得到原序列的逆序?qū)?shù)。 ? 難點(diǎn)：如何合并？ ? 原序列逆序?qū)?shù) =2個(gè)子序列逆序?qū)χ?滿足 V[i]V[j](0in/2+1,n/2jn+1)的數(shù)對(duì)數(shù) 算法優(yōu)化 ——分治策略 ? 滿足 V[i]V[j](0in/2+1,n/2jn+1)的數(shù)對(duì)數(shù)？如何計(jì)算？ ? 方法 1：對(duì)每個(gè) i: while (v[i]v[j++]) … ? 還是 O(n2)的復(fù)雜度 ? 方法 2：如果兩個(gè)子序列是有序的 …… ? 6 4 2 5 3 1 ? 如何保證有序？邊合并邊排序即可 例子 6 4 2 5 3 1 6 4 2 5 3 1 6 4 2 5 3 1 6 4 2 5 3 1 逆序?qū)?=3 逆序?qū)?=3 排序： 6 逆序?qū)?=3+2 排序： 6,5 逆序?qū)?=5+1 排序： 6,5,4,3,2,1 6 5 4 3 2 1 算法效率分析 ? T(n)=2T(n/2)+O(n) ? 用迭代法解該遞推方程得 T(n)=O(nlogn) ? 計(jì)算量 =nlogn=*106log(*106) = *106 ? 效率提高的原因：充分利用有序性，每次可計(jì)算多個(gè)逆序?qū)Α? ? 如果想不到這種方法怎么辦？ 另一種解法 ? 在一個(gè)問題無(wú)法得到解決時(shí)，就需要換一個(gè)角度看問題。 切入點(diǎn)： ? 嘗試將逆序?qū)栴}轉(zhuǎn)化為已有現(xiàn)成的算法的經(jīng)典模型，即排序模型。 ? 嘗試換一種數(shù)據(jù)結(jié)構(gòu)，改變問題的表示方法往往能收到意想不到的效果。 充分注意數(shù)據(jù)范圍 ? 它能在零時(shí)間內(nèi)加速到最大速度 Vi (Vi100) ? 其他的數(shù)據(jù)范圍都很大，唯獨(dú)這個(gè)數(shù)據(jù)范圍很小，這個(gè)矛盾往往是解題的突破口。 ? 在現(xiàn)實(shí)問題，也往往存在這樣現(xiàn)象，大家應(yīng)該對(duì)此充分重視。 ? Tradeoff 新的數(shù)據(jù)結(jié)構(gòu) ? 原來(lái)是用車的編號(hào)來(lái)表達(dá)問題。 . ViVj, XiXj, … ? 能否考慮用速度的值來(lái)表示問題？ ? num[v]：表示當(dāng)前車之前速度為 v的車有多少輛 ? 如何定義超車： ? 車輛 i能被超過的次數(shù)為 ???991][iVkknum算法 int num[100]。 int count=0。 memset(num,0,sizeof(num))。 for (i=0。in。i++) { cinxv。 num[v]++。 for (k=v+1。k100。k++) { count+=num[k]。 } 運(yùn)算量 =O(nk) *107 編制測(cè)試數(shù)據(jù) ? 用手工可以檢驗(yàn)的小數(shù)據(jù)，驗(yàn)證程序的正確性 ? 編寫程序隨機(jī)生成大數(shù)據(jù)，檢驗(yàn)程序的執(zhí)行效率（使用隨機(jī)函數(shù)） ? 注意檢驗(yàn)邊界條件。例如，本題中只有 1輛車時(shí)算法能否得到正確結(jié)果。 小結(jié) ? 整個(gè)超車的過程實(shí)際上就是一個(gè)不斷交換相鄰元素的排序過程。這個(gè)排序方法就是冒泡法。因此超車次數(shù)就是冒泡法中元素一共要被交換的次數(shù)。 ? 通過兩種算法的比較，我們可以看出歸并排序比冒泡法效率高就是因?yàn)闅w并排序排一次操作可以減少多個(gè)逆序?qū)Α? ? 如果本題中 Vi的規(guī)模進(jìn)一步擴(kuò)大，你能想出解決的辦法嗎？ 三色二叉樹 ? 一
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1