【文章內(nèi)容簡(jiǎn)介】 ? 由此可知 D(n)的時(shí)間復(fù)雜性為 O(nlogn)。 顯然由此構(gòu)造的平面最接近點(diǎn)對(duì)算法的復(fù)雜性要大于 O(nlogn)。 2021/11/10 計(jì)算機(jī)算法設(shè)計(jì)與分析 51 算法中合并函數(shù) D的復(fù)雜性 ? 在算法中合并函數(shù) D(n)由以下運(yùn)算構(gòu)成： ? ⑴計(jì)算中位數(shù) m和最小值 dm，需時(shí)為 O(1) 。 ? ⑵將 S分割為 S1和 S2，需時(shí)為 O(n)。 ? ⑶對(duì) P1和 P2中的元素排序， 在最壞情況下需時(shí) O(nlogn)。 ? ⑷在 P1和 P2中找最小距離 dl，需時(shí) O(n)。 ? 由此可知 D(n)的時(shí)間復(fù)雜性為 O(nlogn)。 若要將算法的時(shí)間復(fù)雜性降到 O(nlogn)，需要將 D(n)的時(shí)間復(fù)雜性降到 O(n)。 怎么辦？ 2021/11/10 計(jì)算機(jī)算法設(shè)計(jì)與分析 52 算法中合并函數(shù) D的復(fù)雜性 ? 在算法中合并函數(shù) D(n)由以下運(yùn)算構(gòu)成： ? ⑴計(jì)算中位數(shù) m和最小值 dm，需時(shí)為 O(1) 。 ? ⑵將 S分割為 S1和 S2，需時(shí)為 O(n)。 ? ⑶對(duì) P1和 P2中的元素排序， 在最壞情況下需時(shí) O(nlogn)。 ? ⑷在 P1和 P2中找最小距離 dl，需時(shí) O(n)。 ? 由此可知 D(n)的時(shí)間復(fù)雜性為 O(nlogn)。 在 D(n)中， 唯一時(shí)間復(fù)雜性超過(guò) O(n)的運(yùn)算就是排序 。 2021/11/10 計(jì)算機(jī)算法設(shè)計(jì)與分析 53 算法中合并函數(shù) D的復(fù)雜性 ? 在算法中合并函數(shù) D(n)由以下運(yùn)算構(gòu)成： ? ⑴計(jì)算中位數(shù) m和最小值 dm，需時(shí)為 O(1) 。 ? ⑵將 S分割為 S1和 S2，需時(shí)為 O(n)。 ? ⑶對(duì) P1和 P2中的元素排序， 在最壞情況下需時(shí) O(nlogn)。 ? ⑷在 P1和 P2中找最小距離 dl，需時(shí) O(n)。 ? 由此可知 D(n)的時(shí)間復(fù)雜性為 O(nlogn)。 在遞歸過(guò)程中， P1和 P2中的元素的順序是不變的，因此可以把排序放在遞歸計(jì)算之前，而不放在遞歸的過(guò)程中 。 在整個(gè)算法開(kāi)始之前對(duì)各點(diǎn)的 y坐標(biāo)進(jìn)行一次預(yù)排序，則遞歸中就無(wú)須再排序。 2021/11/10 計(jì)算機(jī)算法設(shè)計(jì)與分析 54 平面最接近點(diǎn)對(duì)的算法 ? float Cpair2(S, d) {n = |S|。 ? if (n2) { d = ∞。 return(d)} ? m = S中各點(diǎn) x坐標(biāo)中位數(shù)；構(gòu)造 S1和 S2； ? Cpair2(S1, d1)。 Cpair2(S2, d2)。 dm=min(d1, d2) ? 構(gòu)造 P1和 P2； ? 將 P1和 P2中的點(diǎn)按 y坐標(biāo)值排序； ? 依次掃描 P1中點(diǎn) u并計(jì)算 u與 P2中 y(u)177。 dm范 圍內(nèi)的點(diǎn)；設(shè) dl是其中的最小距離； ? d = min(dm, dl)。 ? return(d)} 刪去遞歸中的排序運(yùn)算，把它拿到遞歸的外面去！ 2021/11/10 計(jì)算機(jī)算法設(shè)計(jì)與分析 55 平面最接近點(diǎn)對(duì)的算法 ? float Cpair2(S) {n = |S|。 ? if (n2) { d = ∞。 return(d)} ? m = S中各點(diǎn) x坐標(biāo)中位數(shù)；構(gòu)造 S1和 S2； ? d1=Cpair2(S1)。 d2=Cpair2(S2)。 dm=min(d1, d2) ? 構(gòu)造 P1和 P2； ? 依次掃描 P1中點(diǎn) u并計(jì)算 u與 P2中 y(u)177。 dm范 圍內(nèi)的點(diǎn)；設(shè) dl是其中的最小距離； ? d = min(dm, dl)。 ? return(d)} 這個(gè)遞歸中沒(méi)有排序運(yùn)算了。為此需要增加一個(gè)主程序。在主程序中來(lái)完成對(duì)點(diǎn)按y坐標(biāo)的排序。 2021/11/10 計(jì)算機(jī)算法設(shè)計(jì)與分析 56 平面最接近點(diǎn)對(duì)的算法 ? 為此，構(gòu)造主程序： ? float Nearestpair(S) ? { ? Sortbyy(S)。 ? d = Cpair2(S)。 ? ruturn(d)。 ? } 主程序中先對(duì) S中的點(diǎn)按照 y坐標(biāo)進(jìn)行預(yù)排序，然后調(diào)用遞歸程序 Cpair2(S) 。這樣在遞歸程序中就無(wú)需排序了。 對(duì) S中點(diǎn)按 y坐標(biāo)進(jìn)行排序。 2021/11/10 計(jì)算機(jī)算法設(shè)計(jì)與分析 57 最接近點(diǎn)對(duì)的算法復(fù)雜性 ? 修改后的遞歸程序 Cpair2(S) 中的合并函數(shù)D(n)的復(fù)雜性為 O(n)，子問(wèn)題個(gè)數(shù) a為 2，遞減步長(zhǎng) b為 2。由 a = D(b) = b 可知遞歸程序Cpair2(S)的時(shí)間復(fù)雜性為 O(nlogn)。 ? 主程序中 預(yù)排序需時(shí)為 O(nlogn)。 ? 從而整個(gè)算法需時(shí)為 O(nlogn) + O(nlogn)。因而平面 最接近點(diǎn)對(duì)的算法 時(shí)間 復(fù)雜性仍然為 O(nlogn)。 2021/11/10 計(jì)算機(jī)算法設(shè)計(jì)與分析 58 三維空間最接近點(diǎn)對(duì) ? 求三維空間點(diǎn)集合 S中最接近點(diǎn)對(duì)的距離。 ? 求解的方法類(lèi)似求平面問(wèn)題的算法。 ? 與求平面問(wèn)題中不同處是：將 S分割為 S1和 S2兩個(gè)部分的x = m是平面，而非直線。 ? 與求平面問(wèn)題中一樣，分別求出 S S2和它們之間的最近點(diǎn)對(duì)；再取其最小者。 m S1 S2 x y z 2021/11/10 計(jì)算機(jī)算法設(shè)計(jì)與分析 59 三維空間最接近點(diǎn)對(duì) ? 求三維空間點(diǎn)集合 S中最接近點(diǎn)對(duì)的距離。 ? 求解的方法類(lèi)似求平面問(wèn)題的算法。 ? 求 S1和 S2之間的最近點(diǎn)對(duì)時(shí)同樣只考察 m177。 d的區(qū)間 P1和 P2。 ? 對(duì) P1中的點(diǎn) p，考察 P2中 py177。 d或 pz177。 d范圍內(nèi)的點(diǎn)?？疾旆秶橇⒎襟w d 2d 2d，其中點(diǎn)數(shù)不超過(guò)常數(shù)。 m S1 S2 x y z d d P1 P2 p 2d 2d d 是多少？請(qǐng)同學(xué)們自己去考慮。 請(qǐng)同學(xué)們自己去求解此問(wèn)題，并在明天的實(shí)驗(yàn)課上編程實(shí)現(xiàn)。 2021/11/10 計(jì)算機(jī)算法設(shè)計(jì)與分析 60 三維空間最接近點(diǎn)對(duì) ? 求三維空間點(diǎn)集合 S中最接近點(diǎn)對(duì)的距離。 ? 可用類(lèi)似求平面最接近點(diǎn)對(duì)的算法求解。 ? 用平面 x = m將 S分為 S1和 S2兩個(gè)部分。 ? 在求 S1和 S2之間的最接近點(diǎn)對(duì)時(shí)考慮的是 d 2d 2d的立方體。該立方體內(nèi)的點(diǎn)的數(shù)目不超過(guò)一常數(shù) (當(dāng)然不再是 6)。 S1 S2 p m 2d 2d d x ? 此算法的時(shí)間復(fù)雜性仍然是 O(nlogn)。 2021/11/10 計(jì)算機(jī)算法設(shè)計(jì)與分析 61 棋盤(pán)覆蓋問(wèn)題 ? 一個(gè) 2k 2k特殊棋盤(pán)是其中含有一個(gè)特殊方格的棋盤(pán)，左下圖為 k=2的一個(gè)特殊棋盤(pán)。 ? 現(xiàn)在任給定一個(gè) 2k 2k特殊棋盤(pán)，要用右下圖所示的 L型骨牌來(lái)無(wú)重疊的覆蓋它。 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 在 2k 2k的棋盤(pán)覆蓋中要用到 (4k–1)/3個(gè) L型骨牌。 2021/11/10 計(jì)算機(jī)算法設(shè)計(jì)與分析 62 棋盤(pán)覆蓋問(wèn)題 ? 讓我們先來(lái)考慮最簡(jiǎn)單的情況： 什么是最簡(jiǎn)單的情況？ ? 最簡(jiǎn)單情況是 k = 0。這時(shí)棋盤(pán)有 20 20 = 1個(gè)格子，即只有一個(gè)特殊格子。 ? 這時(shí)棋盤(pán)已被完全覆蓋，無(wú)須再做什么了。 ? 下面我們來(lái)考慮復(fù)雜情況是怎樣由較簡(jiǎn)單情況構(gòu)成的。 2021/11/10 計(jì)算機(jī)算法設(shè)計(jì)與分析 63 棋盤(pán)覆蓋問(wèn)題的分析 ? 當(dāng) k0時(shí)，將 2k 2k棋盤(pán)分割成 4個(gè) 2k–1 2k–1的子棋盤(pán)，如右下圖所示： 2k–1 2k–1 2k–1 2k–1 2k–1 2k–1 2k–1 2k–1 ? 特殊方格必定位于 4個(gè)子棋盤(pán)之一中。 ? 而這四個(gè)子棋盤(pán)卻不一致。遞歸求解是將問(wèn)題歸結(jié)到較小規(guī)模的同一問(wèn)題，這就需要將三個(gè)正常子棋盤(pán)也轉(zhuǎn)化成特殊棋盤(pán)。 2021/11/10 計(jì)算機(jī)算法設(shè)計(jì)與分析 64 棋盤(pán)覆蓋問(wèn)題的分析 ? 當(dāng) k0時(shí)，將 2k 2k棋盤(pán)分割成 4個(gè) 2k–1 2k–1的子棋盤(pán)，如右下圖所示： 2k–1 2k–1 2k–1 2k–1 2k–1 2k–1 2k–1 2k–1 ? 特殊方格必定位于 4個(gè)子棋盤(pán)之一中。 ? 為此，可用一個(gè) L型骨牌覆蓋三個(gè)正常子棋盤(pán)的會(huì)合處，如左圖所示。 ? 這次覆蓋后四個(gè)子棋盤(pán)都是特殊棋盤(pán)了。 2021/11/10 計(jì)算機(jī)算法設(shè)計(jì)與分析 65 棋盤(pán)覆蓋的算法 ? 棋盤(pán)覆蓋 (參數(shù)表 ) { ? ⑴ 如果是單個(gè)格子，則返回； ? ⑵將棋盤(pán)劃分成尺寸為一半的子棋盤(pán)； ? ⑶判斷特殊方格在哪個(gè)子棋盤(pán)中，再用相應(yīng) L型骨牌覆蓋相應(yīng)結(jié)合部，即不含特殊方格的部分在結(jié)合部的三個(gè)方格；并記下它們的位置，作為各部分的特殊方格； ? ⑷ 依次對(duì)左上角、右上角、右下角和左下角四個(gè)子棋盤(pán)進(jìn)行棋盤(pán)覆蓋； } 2021/11/10 計(jì)算機(jī)算法設(shè)計(jì)與分析 66 棋盤(pán)覆蓋算法中的參數(shù) ? 算法的形參表中需要的參數(shù)有： ? 遞歸元：棋盤(pán)尺寸為 2n。每輪遞歸時(shí)將 n減 1，則棋盤(pán)尺寸減半；當(dāng) n為 0時(shí)遞歸終止。 ? 棋盤(pán)位置：棋盤(pán)左上角方格的行列號(hào) tr和 tc。 ? 特殊方格位置：特殊方格的行列號(hào) dr和 dc。 參數(shù)表中應(yīng)有哪些參數(shù)呢？ ? 遞歸元定義為 int n ? 棋盤(pán)位置定義為 int tr, tc。 ? 特殊方格位置定義為 int dr, dc。 2021/11/10 計(jì)算機(jī)算法設(shè)計(jì)與分析 67 棋盤(pán)覆蓋算法中其它變量 ? 除了形參表中的那些參數(shù)外，棋盤(pán)覆蓋程序中還需要如下的變量： ? 表示棋盤(pán)的變量。 ? 表示 L型骨牌覆蓋順序的變量。 ? 棋盤(pán)尺寸的變量。 ? 各子棋盤(pán)在結(jié)合部的方格位置。 ? 各子棋盤(pán)的特殊方格的位置。 除形參外，算法中還應(yīng) 有哪些變量呢？ 內(nèi)部變量 全局變量 為什么要設(shè)這個(gè)變量呢？ 2021/11/10 計(jì)算機(jī)算法設(shè)計(jì)與分析 68 棋盤(pán)覆蓋算法中其它變量 ? 棋盤(pán)定義為 int Board[2n][2n]，初值為全 0。 ? 覆蓋順序變量定義為 int tile，其初值為 0。 ? 棋盤(pán)尺寸的變量定義為 int s，其初值為 2n。 不設(shè)此變量也可以。但因 s = 2n，則每輪遞歸中都要做求 2n的冪運(yùn)算。設(shè)變量 s后，只需初始時(shí)計(jì)算一次 s = 2n，以后只要做 s = s/2即可。這樣降低了遞歸中的運(yùn)算強(qiáng)度。 2021/11/10 計(jì)算機(jī)算法設(shè)計(jì)與分析 69 棋盤(pán)覆蓋算法中其它變量 ? 棋盤(pán)定義為 int Board[2n][2n]，初值為全 0。 ? 覆蓋順序變量定義為 int tile，其初值為 0。 ? 棋盤(pán)尺寸的變量定義為 int s，其初值為 2n。 0 1 3 2 四個(gè)子棋盤(pán)的排序?yàn)? ? 結(jié)合部的方格位置定義為 int jr[4], jc[4]。 ? 各子棋盤(pán)的特殊方格的位置定義為 int Sr[4], Sc[4]。 2021/11/10 計(jì)算機(jī)算法設(shè)計(jì)與分析 70 棋盤(pán)覆蓋算法中其它變量 ? 棋盤(pán)定義為 int Board[2n][2n]，初值為全 0。 ? 覆蓋順序變量定義為 int tile，其初值為 0。 ? 棋盤(pán)尺寸的變量定義為 int s。 ? 結(jié)合部的方格位置定義為 int jr[4], jc[4]。 ? 各子棋盤(pán)的特殊方格的位置定義為 int Sr[4], Sc[4]。 ? 將棋盤(pán)覆蓋程序取名為 CoverBoard； 2021/11/10 計(jì)算機(jī)算法設(shè)計(jì)與分析 71 棋盤(pán)覆蓋的算法 ? voice CoverBoard(n, tr, tc, dr, dc) { ? if (n = 0) return。 ? n = n – 1。 s = s/2。 ? tile++。 Coverjoin。 ? CoverBoard(n, tr, tc, sr[0], sc[0])。 ? CoverBoard(n, tr+s, tc, sr[1], sc[1])； ? CoverBoard(n, tr+s, tc+s, sr[2], sc[2]) ? CoverBoard(n, tr, tc+s, sr[3], sc[3])} 若只有一個(gè)格子，則終止遞歸。 注意遞歸元的遞減是在這里做的。 s是減半后的子棋盤(pán)尺寸。 在對(duì)結(jié)合部覆蓋之前將覆蓋序號(hào) tile加一。 2021/11/10 計(jì)算機(jī)算法設(shè)計(jì)與分析 72 棋盤(pán)覆蓋的算法 ? voice CoverBoard(n, tr, tc, dr, dc) { ? if (n = 0) return()。 ? n = n – 1。 s = s/2。 ? tile++。 Coverjoin。 ? CoverBoard(n, tr, tc, sr[0], sc[0])。 ? CoverBoard(n, tr+s, tc, sr[1], sc[1])；