【正文】 2023年 2月 14日星期二 11時 56分 30秒 11:56:3014 February 2023 1一個人即使已登上頂峰，也仍要自強(qiáng)不息。 2023年 2月 14日星期二 上午 11時 56分 30秒 11:56: 1最具挑戰(zhàn)性的挑戰(zhàn)莫過于提升自我。勝人者有力，自勝者強(qiáng)。 :56:3011:56Feb2314Feb23 1越是無能的人，越喜歡挑剔別人的錯兒。 , February 14, 2023 閱讀一切好書如同和過去最杰出的人談話。 2023年 2月 14日星期二 11時 56分 30秒 11:56:3014 February 2023 1空山新雨后，天氣晚來秋。 2023年 2月 14日星期二 上午 11時 56分 30秒 11:56: 1楚塞三湘接，荊門九派通。 11:56:3011:56:3011:56Tuesday, February 14, 2023 1不知香積寺，數(shù)里入云峰。 11:56:3011:56:3011:562/14/2023 11:56:30 AM 1成功就是日復(fù)一日那一點(diǎn)點(diǎn)小小努力的積累。 上午 11時 56分 30秒 上午 11時 56分 11:56: 沒有失敗，只有暫時停止成功！。 2023年 2月 上午 11時 56分 :56February 14, 2023 1行動出成果，工作出財富。 :56:3011:56:30February 14, 2023 1他鄉(xiāng)生白發(fā)，舊國見青山。 :56:3011:56Feb2314Feb23 1故人江海別，幾度隔山川。 , February 14, 2023 雨中黃葉樹，燈下白頭人。各居民點(diǎn)的位臵可以由坐標(biāo) (x,y)表示。 —— 《算法分析與設(shè)計》 83 練習(xí)一：郵局選址問題 問題描述： 在一個按照東西和南北方向劃分成規(guī)整街區(qū)的城市里， n個居民點(diǎn)散亂地分布在不同的街區(qū)中。 3. dm=min(d1,d2)。 //構(gòu)造 S1和 S2； S1={p∈S|x(p)=m}, S2={p∈S|x(p)m} 2. d1=cpair2(S1)。 if (n 2) return 。因此，若將 P1和 P2中所有 S中點(diǎn) 按其 y坐標(biāo)排好序，則對 P1中所有點(diǎn)，對 排好序的點(diǎn)列作一次掃描，就可以找出 所有最接近點(diǎn)對的候選者。 由于能與 p點(diǎn)一起構(gòu)成最接近點(diǎn)對候選者 的 S2中點(diǎn)一定在矩形 R中，所以在直線 l 上的投影點(diǎn)距 p在 l上投影點(diǎn)的距離小于 d。這與 d的意義矛盾。若矩形 R中有多于 6個 S中的點(diǎn)，則由鴿舍原理 易知至少有一個 (d/2) (2d/3)的小矩形中有 2個以上 S中的點(diǎn)。由此可以推 出矩形 R中最多只有 6個 S中的點(diǎn)，因此在分治算法的合并步驟中最多只需要 檢查 6 n/2=3n個候選者。 ?能否在線性時間內(nèi)找到 p,q？ —— 《算法分析與設(shè)計》 80 考慮 P1中任意一點(diǎn) p，若與 P2中的點(diǎn) q構(gòu)成最接近點(diǎn)對的候選者，必有 distance(p， q)＜ d。由此將 S分割為 S1和 S2。 } —— 《算法分析與設(shè)計》 79 (2) 二維情形 ?選取一垂直線 l， x=m來作為分割 直線。 //右側(cè)最小值 ,線性時間 d=min(d1,d2,qp)。 //計算右側(cè)的最接近距離 p=max(S1)。 //線性時間 d1=cpair1(S1)。 if (n2) return ≦。從而用線性時間就可以將 S1的解和 S2的解合并成 為 S的解。由圖可以看出，如果 (md,m]中 有 S中的點(diǎn)，則此點(diǎn)就是 S1中最大點(diǎn)。 ?思考：能否在線性時間內(nèi)找到 p3,q3？ —— 《算法分析與設(shè)計》 77 ?如果 S的最接近點(diǎn)對是 {p3,q3}，即 |p3q3|d，則 p3和 q3兩者 與 m的距離不超過 d，即 p3∈(m d,m]， q3∈(m,m+d] 。 證明得知，該問題的時間下界為 Ω(n ㏒ n) —— 《算法分析與設(shè)計》 76 優(yōu)化最接近點(diǎn)對問題算法 ?假設(shè)用 x軸上某個點(diǎn) m將 S劃分為 2個子集 S1和 S2，基于平 衡子問題的思想，用 S中各點(diǎn)坐標(biāo)的中位數(shù)來作分割點(diǎn)。 解決方法： 對所有點(diǎn)進(jìn)行排序，需要 O(n㏒ n)。最接近點(diǎn)對為其中相差最小的 2個實(shí)數(shù)。時間復(fù)雜性 O(n2)。 —— 《算法分析與設(shè)計》 74 給定平面上 n個點(diǎn)的集合 S，找其中的一對點(diǎn)，使得在 n個點(diǎn)組成的所有點(diǎn)對中，該點(diǎn)對間的距離最小。 T(3n/4)：劃分的子序列最多為 3n/4。 else return select(a, i+1, r, kj)。 j=ip+1。 } int x = select(a, p, p+(rp+1)/51, (rp)/10)。 bubbleSort(s,t)。 i(rp+1)/5。 return a[p+k1]。 else return select(a, i+1, r, kj)。 int i = partition(p,r,x), j=計算前半?yún)^(qū)個數(shù) 。 } 分組排序，并將中位數(shù)交換到前面 。 ? ?5n? ?n? ?5n ? ?5n? ?10/)5( ?n? ?10/)5( ?n? ?/)5(n? ?10/)5( ?n? ?5n—— 《算法分析與設(shè)計》 72 T select (T a[], int p, int r, int k) { if (少于或等于 5個數(shù)值 ) { 直接排序 。 當(dāng) n≥75 時， 3(n5)/10≥n/4 。在這種情況下， 基準(zhǔn) x至少比 3 個元素大， 因為在每一組中有 2個元素小于本組 的中位數(shù)，而 個中位數(shù) 中又有 個小于基準(zhǔn) x。用任意一種排序算法，將每組中的元素排好序，并取出每組的中位數(shù)，共 個。以這個元素作為劃分基準(zhǔn)。 —— 《算法分析與設(shè)計》 71 找出這 個元素的中位數(shù)。 例子（續(xù)） (5) 由于 |P|=13,|Q|=1,k=18，所以放棄 P,Q，使 k=18131=4，對 R遞歸地執(zhí)行本算法； (6) 將 R劃分成 3(floor(15/5))組： {31,60,33,51,57},{49,35,43,37,52},{32,54,41,46,29} (8) 根據(jù) 43將 R劃分成 3組： {31, 33, 35,37,32, 41, 29},{43},{60, 51,57, 49, 52,54, 46} —— 《算法分析與設(shè)計》 70 (12) 因為 k=4,而第一、第二個子數(shù)組的元素個數(shù)為 3，所以 33即為所求取的第 18個小元素。由此可得 T(n)=O(n)。 例如，若 ε=9/10 ，算法遞歸調(diào)用所產(chǎn)生的子數(shù)組的長度至少縮短 1/10。 在最壞情況下，算法 randomizedSelect需要 O(n2)計算時間。最后對所得到的 n/r 個中間元素，遞歸使用選擇算法，求得”中間之中間”作為支點(diǎn)元素。 } p i r j a —— 《算法分析與設(shè)計》 66 一種選擇支點(diǎn)元素的方法是使用“ 中間的中間 （ medianofmedian）” 首先將數(shù)組 a中的 n 個元素分成 n/r 組， r 為某一整常數(shù)，除了最后一組外，每組都有 r個元素。 if ( k = j) return randomizedSelect(a, p, i, k)。 int i = randomizedPartition(a, p, r)。 } p i r j a 問題：給定線性序集中 n個元素和一個整數(shù) k， 1≤k≤n ，要求找出這 n個元素中第 k小的元素。 ? ?23n? ?)12log ( ?n（ 1）分別找出最大值和最小值，比較次數(shù)為 2（ n1） 同時找到最大值和最小值方法 ： —— 《算法分析與設(shè)計》 64 T randomizedSelect(T a[], int p, int r, int k) { 如果只有一個元素，將其返回； int i = 隨機(jī)將線性序列分解為兩部分 (前小后大）； j = 計算前段元素個數(shù) 。 分治算法舉例 6：線性時間選擇 在有 n個元素的集合中找最小值或最大值需比較 n1次。 // 將兩個有序段合并到 b copy(a,b,left,right)。 // 歸并排序前后兩部分 mergeSort(a,mid + 1, right)。 —— 《算法分析與設(shè)計》 60 template class T void mergeSort(T a[],int left, int right) { if (left right) { mid = (left + right) / 2。 chessBoard(board,tr+s,tc+s,tr+s,tc+s,s,tile)。 } // 右下角 if (dr = tr+s dc = tc + s) chessBoard(board,tr+s,tc+s,dr,dc,s,tile)。 else { board[tr+s][tc+s1] = t。 chessBoard(board,tr,tc+s,tr+s1,tc+s,s,tile)。 } // 右上角 if (dr tr + s dc = tc + s) chessBoard(board,tr,tc+s,dr,dc,s,tile)。 else{ board[tr+s1][tc+s1] = t。 int t = tile++。} —— 《算法分析與設(shè)計》 56 —— 《算法分析與設(shè)計》 57 void chessBoard(int board[N][N],int tr,int tc,int dr,int dc,int size,int tile) { if (size == 1) return。