【文章內(nèi)容簡介】 731522 MMMMC ????復(fù)雜度分析 T(n)=O(nlog7) =O()?較大的改進(jìn) ? 22)()2/(7)1()(2 ??????? nnnOnTOnTStrassen矩陣乘法 ?傳統(tǒng)方法 ： O(n3) ?分治法 : O() ?更快的方法 ?? ?Hopcroft和 Kerr已經(jīng)證明 (1971)，計(jì)算 2個(gè)２ ２矩陣的乘積， 7次乘法是必要的。因此，要想進(jìn)一步改進(jìn)矩陣乘法的時(shí)間復(fù)雜性，就不能再基于計(jì)算 2 2矩陣的 7次乘法這樣的方法了?；蛟S應(yīng)當(dāng)研究３ ３或５ ５矩陣的更好算法。 ?在 Strassen之后又有許多算法改進(jìn)了矩陣乘法的計(jì)算時(shí)間復(fù)雜性。目前最好的計(jì)算時(shí)間上界是 O() ?是否能找到 O(n2)的算法？？？目前為止還沒有結(jié)果。 快速排序 private static int partition (int p, int r) { int i = p, j = r + 1。 Comparable x = a[p]。 // 將 = x的元素交換到左邊區(qū)域 // 將 = x的元素交換到右邊區(qū)域 while (true) { while (a[++i].pareTo(x) 0)。 while (a[j].pareTo(x) 0)。 if (i = j) break。 (a, i, j)。 } a[p] = a[j]。 a[j] = x。 return j。 } 初始序列 {6, 7, 5, 2, 5, 8} j。 ji{5, 7, 5, 2, 6, 8} i++。 ji{5, 6, 5, 2, 7, 8} j。 ji{5, 2, 5, 6, 7, 8} i++。 ji完成 快速排序具有 不穩(wěn)定性 。 {6, 7, 5, 2, 5, 8} {5, 2, 5} 6 {7, 8} private static int randomizedPartition (int p, int r) { int i = random(p,r)。 (a, i, p)。 return partition (p, r)。 } 快速排序 快速排序算法的性能取決于劃分的對稱性。通過修改算法 partition，可以設(shè)計(jì)出采用隨機(jī)選擇策略的快速排序算法。在快速排序算法的每一步中，當(dāng)數(shù)組還沒有被劃分時(shí)，可以在 a[p:r]中隨機(jī)選出一個(gè)元素作為劃分基準(zhǔn)，這樣可以使劃分基準(zhǔn)的選擇是隨機(jī)的，從而可以期望劃分是較對稱的。 ?最壞時(shí)間復(fù)雜度： O(n2) ?平均時(shí)間復(fù)雜度： O(nlogn) ?輔助空間： O(n)或 O(logn) ?穩(wěn)定性：不穩(wěn)定 最接近點(diǎn)對問題 給定平面上 n個(gè)點(diǎn)的集合 S，找其中的一對點(diǎn)，使得在 n個(gè)點(diǎn)組成的所有點(diǎn)對中，該點(diǎn)對間的距離最小。 ?為了使問題易于理解和分析，先來考慮 一維 的情形。此時(shí)，S中的 n個(gè)點(diǎn)退化為 x軸上的 n個(gè)實(shí)數(shù) x1,x2,…,xn 。最接近點(diǎn)對即為這 n個(gè)實(shí)數(shù)中相差最小的 2個(gè)實(shí)數(shù)。 ?假設(shè)我們用 x軸上某個(gè)點(diǎn) m將 S劃分為 2個(gè)子集 S1和 S2 ， 基于 平衡子問題 的思想，用 S中各點(diǎn)坐標(biāo)的中位數(shù)來作分割點(diǎn)。 ?遞歸地在 S1和 S2上找出其最接近點(diǎn)對 {p1,p2}和 {q1,q2}，并設(shè) d=min{|p1p2|,|q1q2|}， S中的最接近點(diǎn)對或者是 {p1,p2}，或者是 {q1,q2}，或者是某個(gè) {p3,q3}，其中 p3∈ S1且 q3∈ S2。 ?能否在線性時(shí)間內(nèi)找到 p3,q3？ 最接近點(diǎn)對問題 ?如果 S的最接近點(diǎn)對是 {p3,q3}，即 |p3q3|d，則 p3和 q3兩者與 m的距離不超過 d， 即 p3∈ (md,m]， q3∈ (m,m+d]。 ?由于在 S1中，每個(gè)長度為 d的半閉區(qū)間至多包含一個(gè)點(diǎn)（否則必有兩點(diǎn)距離小于 d），并且 m是 S1和 S2的分割點(diǎn)，因此(md,m]中至多包含 S中的一個(gè)點(diǎn)。由圖可以看出， 如果 (md,m]中有 S中的點(diǎn)，則此點(diǎn)就是 S1中最大點(diǎn)。 ?因此，我們用線性時(shí)間就能找到區(qū)間 (md,m]和 (m,m+d]中所有點(diǎn)，即 p3和 q3。 從而我們用線性時(shí)間就可以將 S1的解和 S2的解合并成為 S的解 。 能否在線性時(shí)間內(nèi)找到 p3,q3？ 最接近點(diǎn)對問題 ?下面來考慮二維的情形。 ?選取一垂直線 l:x=m來作為分割直線。其中 m為 S中各點(diǎn) x坐標(biāo)的中位數(shù)。由此將 S分割為 S1和 S2。 ?遞歸地在 S1和 S2上找出其最小距離 d1和 d2，并設(shè)d=min{d1,d2}， S中的最接近點(diǎn)對或者是 d，或者是某個(gè) {p,q}，其中 p∈ P1且 q∈ P2。 ?能否在線性時(shí)間內(nèi)找到 p,q？ 最接近點(diǎn)對問題 ?考慮 P1中任意一點(diǎn) p，它若與 P2中的點(diǎn) q構(gòu)成最接近點(diǎn)對的候選者，則必有 distance(p， q)＜ d。 滿足這個(gè)條件的 P2中的點(diǎn)一定落在一個(gè) d 2d的矩形 R中 ?由 d的意義可知， P2中任何 2個(gè) S中的點(diǎn)的距離都不小于 d。由此可以推出 矩形 R中最多只有 6個(gè) S中的點(diǎn) 。 ?因此，在分治法的合并步驟中 最多只需要檢查 6 n/2=3n個(gè)候選者 能否在線性時(shí)間內(nèi)找到 p3,q3？ 證明 :將矩形 R的長為 2d的邊 3等分，將它的長為d的邊 2等分，由此導(dǎo)出 6個(gè) (d/2) (2d/3)的矩形。若矩形 R中有多于 6個(gè) S中的點(diǎn)，則由鴿舍原理易知至少有一個(gè) (d/2) (2d/3)的小矩形中有 2個(gè)以上 S中的點(diǎn)。設(shè) u， v是位于同一小矩形中的 2個(gè)點(diǎn)，則 distance(u,v)d。這與 d的意義相矛盾。 22222 3625)3/2()2/())()(())()(( dddvyuyvxux ???????為了 確切地知道要檢查哪 6個(gè)點(diǎn) ，可以將 p和P2中所有 S2的點(diǎn)投影到垂直線 l上。由于能與p點(diǎn)一起構(gòu)成最接近點(diǎn)對候選者的 S2中點(diǎn)一定在矩形 R中，所以它們在直線 l上的投影點(diǎn)距 p在 l上投影點(diǎn)的距離小于 d。由上面的分析可知，這種投影點(diǎn)最多只有 6個(gè)。 ?因此，若將 P1和 P2中所有 S中點(diǎn)按其 y坐標(biāo)排好序，則對 P1中所有點(diǎn)，對排好序的點(diǎn)列作一次掃描，就可以找出所有最接近點(diǎn)對的候選者。對 P1中每一點(diǎn)最多只要檢查 P2中排好序的相繼 6個(gè)點(diǎn)。 最接近點(diǎn)對問題 最接近點(diǎn)對問題 public static double cpair2(S) { n=|S|。 if (n 2) return 。 1. m=S中各點(diǎn) x間坐標(biāo)的中位數(shù) 。 構(gòu)造 S1和 S2； //S1={p∈ S|x(p)=m}, S2={p∈ S|x(p)m} 2. d1=cpair2(S1)。 d2=cpair2(S2)。 3. dm=min(d1,d2)。 4. 設(shè) P1是 S1中距垂直分割線 l的距離在 dm之內(nèi)的所有點(diǎn)組成的集合； P2是 S2中距分割線 l的距離在 dm之內(nèi)所有點(diǎn)組成的集合； 將 P1和 P2中點(diǎn)依其 y坐標(biāo)值排序； 并設(shè) X和 Y是相應(yīng)的已排好序的點(diǎn)列； 5. 通過掃描 X以及對于 X中每個(gè)點(diǎn)檢查 Y中與其距離在 dm之內(nèi)的所有點(diǎn) (最多 6個(gè) )可以完成合并； 當(dāng) X中的掃描指針逐次向上移動(dòng)時(shí)， Y中的掃描指針可在寬為 2dm的區(qū)間內(nèi)移動(dòng)； 設(shè) dl是按這種掃描方式找到的點(diǎn)對間的最小距離； 6. d=min(dm,dl)。 return d。 } 復(fù)雜度分析 T(n)=O(nlogn) ??????? 44)()2/(2)1()(nnnOnTOnT設(shè)計(jì)一個(gè)滿足以下要求的比賽日程表： (1)每個(gè)選手必須與其他 n1個(gè)選手各賽一次； (2)每個(gè)選手一天只能賽一次； (3)循環(huán)賽一共進(jìn)行 n1天。 按分治策略，將所有的選手分為兩半， n個(gè)選手的比賽日程表就可以通過為 n/2個(gè)選手設(shè)計(jì)的比賽日程表來決定。遞歸地用對選手進(jìn)行分割，直到只剩下 2個(gè)選手時(shí)，比賽日程表的制定就變得很簡單。這時(shí)只要讓這 2個(gè)選手進(jìn)行比賽就可以了。 1 2 3 4 5 6 7 8 2 1 4 3 6 5 8 7 3 4 1 2 7 8 5 6 4 3 2 1 8 7 6 5 5 6 7 8 1 2 3 4 6 5 8 7 2 1 4 3 7 8 5 6 3 4 1 2 8 7 6 5 4 3 2 1 循環(huán)賽日程表 設(shè)計(jì)一個(gè)滿足以下要求的比賽日程表： (1)每個(gè)選手必須與其他 n1個(gè)選手各賽一次； (2)每個(gè)選手一天只能賽一次； (3)循環(huán)賽一共進(jìn)行 n1天。 按分治策略，將所有的選手分為兩半， n個(gè)選手的比賽日程表就可以通過為 n/2個(gè)選手設(shè)計(jì)的比賽日程表來決定。遞歸地用對選手進(jìn)行分割，直到只剩下 2個(gè)選手時(shí)，比賽日程表的制定就變得很簡單。這時(shí)只要讓這 2個(gè)選手進(jìn)行比賽就可以了。 1 2 3 4 5 6 7 8 2 1 4 3 6 5 8 7 3 4 1 2 7 8 5 6 4 3 2 1 8 7 6 5 5 6 7 8 1 2 3 4 6 5 8 7 2 1 4 3 7 8 5 6 3 4 1 2 8 7 6 5 4 3 2 1 ? 但是經(jīng)分解得到的子問題往往不是互相獨(dú)立的。不同子問題的數(shù)目常常只有多項(xiàng)式量級。在用分治法求解時(shí)，有些子問題被重復(fù)計(jì)算了許多次。 動(dòng)態(tài)規(guī)劃思想 n T(n) = n/2 T(n/4) T(n/4) T(n/4) T(n/4) n/2 T(n/4) T(n/4) T(n/4) T(n/4) n/2 T(n/4) T(n/4) T(n/4) T(n/4) n/2 T(n/4) T(n/4) T(n/4) T(n/4) ? 如果能夠保存已解決的子問題的答案，而在需要時(shí)再找出已求得的答案，就可以避免大量重復(fù)計(jì)算，從而得到多項(xiàng)式時(shí)間算法。 n = n/2 T(n/4) T(n/4) T(n/4) T(n/4) n/2 n/2 T(n/4) T(n/4) n/2 T(n/4) T(n/4) T(n/4) T(n/4) T(n/4) T(n) 動(dòng)態(tài)規(guī)劃思想 動(dòng)態(tài)規(guī)劃基本步驟 ? 找出最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。 ? 遞歸地定義最優(yōu)值。 ? 以自底向上的方式計(jì)算出最優(yōu)值。 ? 根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造最優(yōu)解。 動(dòng)態(tài)規(guī)劃算法的基本要素 一、最優(yōu)子結(jié)構(gòu) ?矩陣連乘計(jì)算次序問題的最優(yōu)解包含著其子問題的最優(yōu)解。這種性質(zhì)稱為 最優(yōu)子結(jié)構(gòu)性質(zhì) 。 ?在分析問題的最優(yōu)子結(jié)構(gòu)性質(zhì)時(shí)，所用的方法具有普遍性：首先假設(shè)由問題的最優(yōu)解導(dǎo)出的子問題的解不