序列和字符串

1、2005年浙江省隊(duì)培訓(xùn)第3講 序列和字符串的算法1目錄一、算法分析基礎(chǔ)二、排序三、序列的算法四、串的算法2一、算法分析基礎(chǔ)3抽象操作抽象操作(abstract operations). 對(duì)于單一操作(如加法)的算法, 運(yùn)行時(shí)間 = 操作時(shí)間 * 操作次數(shù) (不考慮cache等體系結(jié)構(gòu)方面的影響)操作時(shí)間取決于計(jì)算機(jī)操作次數(shù)取決于算法算法分析: 只考慮算法特性, 因此只考慮操作次數(shù)4操作數(shù)函數(shù)在很多情況下, 基本操作數(shù)可以寫成N的函數(shù)f(N), 其中N代表主要參數(shù)例如, 給N個(gè)數(shù)排序的問題, N就是主要參數(shù), 它最明顯的決定了問題的復(fù)雜程度, 也影響著算法效率存在多個(gè)主參數(shù)的情況類似定義, 本節(jié)

2、暫不考慮5比較兩個(gè)算法假設(shè)有兩個(gè)算法算法一執(zhí)行了f(n)=n2次基本操作算法二執(zhí)行了g(n)=n2/2次基本操作那個(gè)算法好呢？絕對(duì)操作數(shù)算法二好，因?yàn)間(n) f(n)增長情況呢？n擴(kuò)大10倍，f(n)擴(kuò)大100倍，g(n)也擴(kuò)大100倍兩個(gè)算法的增長情況一樣！我們說: 漸進(jìn)時(shí)間復(fù)雜度一樣！6漸進(jìn)時(shí)間復(fù)雜度f(n)=n2和g(n)=n2/2結(jié)論: 增長情況一樣問題: 如何表示“增長情況”？方法: 把f(n)和g(n)變成“漸進(jìn)”形式，然后直接比較如何變成“漸進(jìn)”形式？只保留最“大”項(xiàng), 忽略系數(shù), 符合前面介紹的原則例1：3n4+8n2+n+2 n4例2：2n+1+n100+5 2n (為什么

3、n+1變成了n？)7常見的函數(shù)增長f(N)的漸進(jìn)形式往往是以下某個(gè)函數(shù)1(常數(shù), constant): 和N無關(guān), N多大運(yùn)行時(shí)間都一樣logN(對(duì)數(shù), logarithmic): 這是個(gè)增長緩慢的函數(shù). 若底為2, 則log1000000約為20N(線性, linear): 對(duì)于必須處理N個(gè)輸入數(shù)據(jù), 或者得到N個(gè)輸出數(shù)據(jù)的問題, 算法(在漸進(jìn)意義下)是最優(yōu)的.N2(平方, quadratic): 若N加倍, 函數(shù)值變?yōu)樗谋?N(指數(shù)級(jí), exponential): N很小時(shí)2N已經(jīng)很大了多項(xiàng)式算法Na: 有效算法8函數(shù)增長和運(yùn)行時(shí)間9對(duì)數(shù)函數(shù)若bL=n, 記L = logbn，稱L為以b為

4、底的n的對(duì)數(shù)對(duì)數(shù)的公式logan + logam = loganmklogan = logank換底公式： logan/logbn=logba對(duì)數(shù)是一種增長很慢的函數(shù)log21000 約為 10log21000000 約為2010對(duì)數(shù)函數(shù)由于算法分析忽略常數(shù)，通常logN不指定底, 默認(rèn)情況為2, 記為lgN, 若底為自然對(duì)數(shù)e(=2.71828), 記為lnNlgN為N二進(jìn)制表示中的位數(shù),lg10=3.322有時(shí)也取對(duì)數(shù)的對(duì)數(shù) loglogN. 由于lglg1012=lg39.865.32, 所以一般可以把它看作常數(shù)11其他常見函數(shù)和近似12復(fù)雜度分析不清楚怎么辦只分析上限，而不需要精確計(jì)算

5、實(shí)際運(yùn)行時(shí)間若n充分大時(shí)|f(n)|=c|g(n)|，其中c為某常數(shù)記f(n) = O(g(n)，表示g(n)為f(n)的漸進(jìn)上限例1：5n2+3n+1 = O(n2)例2：2n3 = O(7n8)類似的，可以定義下限如果上下限相等，增長情況完全一樣,記做由于上限有無限多個(gè)，我們希望它盡量精確, 否則我們的分析就過于悲觀了，實(shí)際算法沒那么糟糕13遞歸式在很多時(shí)候, 無法寫出時(shí)間復(fù)雜度T(n)的顯式表達(dá)式, 而只能得到遞歸方程公式一: T(1)=1, T(n)=T(n-1)+n, 則T(n)為n(n+1)/2公式二: T(1)=1, T(n)=T(n/2)+1, 則T(n)約為lgN公式三: T

6、(1)=0, T(n)=T(n/2)+n, 則T(n)約為2n公式四: T(1)=0, T(n)=2T(n/2)+n, 則T(n)約為nlgN公式五: T(1)=1, T(n)=2T(n/2)+1, 則T(n)約為2n考慮一般情形: T(n) = aT(n/b) + f(n)14遞歸樹分析T(n) = aT(n/b) + f(n), a, b為常數(shù)，f(n)為給定函數(shù)遞歸樹: T(n) = f(n)+af(n/b)+a2f(n/b2)+aLf(n/bL)其中最后一項(xiàng)為遞歸邊界，即n/bL=1，因此L=logbn15公式四分析T(n) = aT(n/b) + f(n)遞歸樹得到的結(jié)果：T(n)

7、= f(n)+af(n/b)+a2f(n/b2)+aLf(n/bL)其中L=logbn公式四：T(n) = 2T(n/2) + na = 2, b = 2, f(n) = n對(duì)于第k項(xiàng)，有2kf(n/2k) = 2k *n/2k = n一共有l(wèi)og2n項(xiàng)T(n) = n * log2n = O(nlogn)16最大連續(xù)序列問題給一串整數(shù)a1n，求出它和最大的子序列，即找出1=i=j max then max := sum; end;思想：枚舉所有的i和j，計(jì)算ai+aj，選擇最大的時(shí)間復(fù)雜度如何分析？三層循環(huán)內(nèi)層操作次數(shù)取決于i, j中層操作次數(shù)取決于i18算法一分析當(dāng)i和j一定的時(shí)候，內(nèi)層循

8、環(huán)執(zhí)行j-i+1次總次數(shù)為應(yīng)該如何計(jì)算？方法一：直接計(jì)算先計(jì)算里層求和號(hào)，得再加起來？好復(fù)雜直接算法需要利用公式12+n2=O(n3)一般地，有1k+nk=O(nk+1). 證明: 數(shù)學(xué)歸納法19算法一分析（續(xù)）總次數(shù)為：完全的計(jì)算太麻煩能不能不動(dòng)筆就知道漸進(jìn)時(shí)間復(fù)雜度呢？何必非要計(jì)算出詳細(xì)的公式再化簡(jiǎn)呢？里層求和計(jì)算出的結(jié)果是O(n-i)2)12+22+n2=O(n3)每步都化簡(jiǎn)！但是要保留外層需要的變量結(jié)論：算法一時(shí)間復(fù)雜度為O(n3)經(jīng)驗(yàn)：一般只能支持 n max then max := sj si-1;時(shí)間復(fù)雜度：預(yù)處理+主程序=O(n+n2)=O(n2). n=500022算法三用一

9、種完全不同的思路最大子序列的位置有三種可能完全處于序列的左半，即j=n/2跨越序列中間，即in/2j用遞歸的思路解決！設(shè)max(i, j)為序列aij的最大子序列, 那么23算法三（續(xù)）用遞歸的思路解決！設(shè)max(i, j)為序列aij的最大子序列設(shè)mid = (i + j)/2，即區(qū)間aij的中點(diǎn)最大的第一種序列為max(i, mid)最大的第二種序列為max(mid+1, j)問題：最大的第三種序列為？既然跨越中點(diǎn)，把序列aij劃分為兩部分aimid：最大序列用掃描法在n/2時(shí)間內(nèi)找到一共只有mid-1=n/2種可能的序列，一一比較即可amid+1j：同理一共花費(fèi)時(shí)間為j-i+124算法三

10、分析如何分析時(shí)間復(fù)雜度呢？我們沒有直接得到具體的T(n)的式子但是容易得到遞推關(guān)系T(n) = 2T(n/2) + n設(shè)時(shí)間復(fù)雜度的精確式子是T(n)第一、二種序列的計(jì)算時(shí)間是T(n/2)，因?yàn)樾蛄虚L度縮小了一半第三種序列的計(jì)算時(shí)間是n由遞歸式四, 得T(n)=O(nlogn)25算法四算法二的實(shí)質(zhì)是求出i=j,讓sj-si-1最大對(duì)于給定的j，能否直接找到在j之前的最小s值呢？從小到大掃描jj=1時(shí)，只有一個(gè)合法的i，即i=1, s1-1=0如果sj變大，則最小的s值和上次一樣如果sj再創(chuàng)新低，應(yīng)該讓sj作為今后的最優(yōu)s值min_s := 0;For j :=1 to n do begin

11、if sj max then max := sj min_s;end;時(shí)間復(fù)雜度很明顯：O(n). n = 1,000,00026總結(jié)算法時(shí)間復(fù)雜度規(guī)模分析方法枚舉O(n3)約200分層求和優(yōu)化枚舉O(n2)約3000明顯分治O(nlogn)約105遞歸樹掃描O(n)約106明顯27二、排序28問題1: 排序給n個(gè)數(shù), 從小到大排序29思考: 籃球俱樂部給定N個(gè)人的身高（1.95m2.05m），要求將他們排成一列，使得任意選取兩個(gè)人，他們中間如果存在K個(gè)人，并且身高和為S，那么S與K2m的差的絕對(duì)值小于等于0.1m。 30插入排序和選擇排序增量算法 選擇排序？取決于未來的輸入？ 插入排序：來一

12、個(gè)插一個(gè)部分排序 插入排序？如果前k大的是最后k個(gè)元素 選擇排序：選的前k個(gè)就是前k大元素結(jié)論：排序算法的選擇要看實(shí)際應(yīng)用31歸并排序二路歸并1, 2, 4, 7, 93, 5, 6, 10, 11合并：n分治sort(i, j)，設(shè)時(shí)間為T(n) 排前一半：sort(i, mid), 時(shí)間T(n/2) 排后一半：sort(mid+1, j)，時(shí)間T(n/2) 合并起來：n32歸并排序算法分析時(shí)間: T(n) = 2T(n/2) + n T(n) = O(nlogn)空間: S(n) = 2S(n/2) + n? 空間可重用!最好、最壞、平均是一致的33例題: 煎餅?zāi)繕?biāo)：從小到大排序從下數(shù)第k

13、個(gè)開始往上翻(a) (b) (c) 3 1 34問題2: 逆序?qū)?shù)目逆序?qū)?shù)目：i aj枚舉：O(n2). n = 5000利用歸并排序的框架 j = mid，遞歸處理i mid j，合并的時(shí)候順便求！ 1, 2, 4, 7, 9 3, 5, 6, 10, 11取后一半元素時(shí)，前一半還剩多少個(gè)就是時(shí)間復(fù)雜度：O(nlogn)35快速排序找一個(gè)數(shù)x 讓x左邊的數(shù)都比x小 讓x右邊的數(shù)都比x大 分別給兩邊排序 核心：如何調(diào)整x左右的數(shù)？從兩邊往中間掃描 在x左邊第一個(gè)比x大的地方停下來 在x右邊第一個(gè)比x小的地方停下來兩個(gè)交換，正好都滿足要求36快速排序例子：1, 8, 2, 9, 6, 4, 7

14、, 3, 5第一次交換8和5：1, 5, 2, 9, 6, 4, 7, 3, 8第二次交換9和3：1, 5, 2, 3, 6, 4, 7, 9, 8 第三次交換6和4：1, 5, 2, 3, 4, 6, 7, 9, 8兩個(gè)指針匯合，完成時(shí)間復(fù)雜度：O(n)37快速排序分析最好情況：均分成兩半，則是O(nlogn)最壞情況：分成長度為1和n-1，則是O(n2)這是不是說明快速排序比歸并排序差顯然不是，否則就不會(huì)叫“快速排序”了嘛加入隨機(jī)數(shù), 幾乎可以保證是O(nlogn), 系數(shù)比歸并排序小隨機(jī)數(shù)讓壞情況從數(shù)據(jù)轉(zhuǎn)移到了隨機(jī)運(yùn)氣38快速排序一些小細(xì)節(jié)n = 10時(shí)用插入排序加速x如何選？中間？隨機(jī)

15、（隨機(jī)數(shù)產(chǎn)生開銷）？警告！快速排序不穩(wěn)定！原因？如何修改？最壞情況:數(shù)據(jù)隨機(jī)數(shù)39問題3: 求序列中第k大數(shù)方法一: 先排序O(nlogn)方法二: 借用快速排序的框架只需要根據(jù)k的大小只處理一邊平均情況：O(n)40例題: 士兵排隊(duì)問題n=10,000個(gè)士兵在網(wǎng)格中位置用(x, y)表示 士兵可以沿四個(gè)方向移動(dòng) 進(jìn)入某一行且排在一起 假設(shè)格子可以容納所有士兵41分析行：感覺在”中間”中位數(shù) or 平均數(shù)？假設(shè)往下一行列？（請(qǐng)思考）42思考: 加權(quán)中位數(shù)X軸上有n個(gè)點(diǎn)，第i個(gè)點(diǎn)都的權(quán)值為正數(shù)Vi，要求在X軸上找出一點(diǎn)P，使sumVi*|xp-xi|最小43計(jì)數(shù)排序特殊的排序?qū)ο螅?100的整數(shù)

16、(如分?jǐn)?shù))開一個(gè)count0.100的數(shù)組，記錄個(gè)數(shù) for i:=1 to n do inc(countscorei);時(shí)間復(fù)雜度為O(n), 比快速排序還快關(guān)鍵: 利用了關(guān)鍵碼的范圍44基于比較的排序時(shí)間下限簡(jiǎn)單起見，不考慮相等的情形可以獲得多少信息？ 一次比較，兩種結(jié)果 k次比較2k種結(jié)果需要獲得多少信息？ n個(gè)數(shù)的排列有n!種 最后只剩一種可能性時(shí)，排序完成45基于比較的排序時(shí)間下限需要比較多少次？ 比較k次以后最好只能保證剩n!/2k種可能性 n!/2k=1時(shí)，即k=log(n!)時(shí)排序完成log(n!) = (nlogn)46三、序列的算法47問題1: RMQ問題給n個(gè)數(shù)a1n設(shè)計(jì)

17、在線算法, 對(duì)于每個(gè)詢問(L, R), 回答aLR內(nèi)的最小值48分析算法一: O(n2)-O(1)RMQi,j = minRMQi,j-1, Aj用長度遞增的順序計(jì)算所有RMQi,j算法二: O(n)-O(n1/2)分為長度L=n1/2的小塊, 共L塊預(yù)處理得到每個(gè)塊的最小值詢問最多涉及L個(gè)塊和頭尾塊的2L個(gè)元素好處: 修改也是O(n1/2)的49分析算法三: O(nlogn)-O(1)di,j為從i開始的, 長度為2j的范圍內(nèi)的RMQ遞推式di,j=mindi,j-1,di+2j-1,j-1. 預(yù)處理是O(nlogn)的詢問時(shí)取k=log2(j-i+1), A為從i開始長度為2k的塊, B為

18、以j結(jié)束的長度為2k的塊, 則A和B覆蓋區(qū)間(i,j). 詢問是O(1)的算法四: O(n)-O(1)用Cartesian-Tree轉(zhuǎn)化成LCA問題50問題2: k路歸并問題把有k個(gè)有序表, 合并成一個(gè)有序表.元素共有n個(gè).51分析每個(gè)表的元素都是從左到右移入新表把每個(gè)表的當(dāng)前元素放入堆中, 每次刪除最小值并放入新表中, 然后加入此序列的下一個(gè)元素每次操作需要logk時(shí)間, 因此總共需要nlogk的時(shí)間52問題3: 序列和的前n小元素給出兩個(gè)長度為n的有序表A和B, 在A和B中各任取一個(gè), 可以得到n2個(gè)和. 求這些和最小的n個(gè)53分析可以把這些和看成n個(gè)有序表:A1+B1 = A1+B2 =

19、 A1+B3 =A2+B1 = A2+B2 = A2+B3 =An+B1 = An+B2 = An+B3 =類似剛才的算法, 每次O(logn), 共取n次最小元素,共O(nlogn)54問題4: 多個(gè)有序表的第k大元素有m個(gè)有序表, 每個(gè)表里有n個(gè)元素.所有元素不超過W設(shè)計(jì)在線算法, 回答這m*n個(gè)元素中第k個(gè)元素的值55分析二分元素大小x計(jì)算每個(gè)有序表里比x小的元素個(gè)數(shù)k, 每個(gè)表O(logn), 共O(mlogn)如果k=k, 輸出x如果kk, 把x變小總時(shí)間復(fù)雜度O(mlogn*logW)56問題5: 范圍內(nèi)第k大數(shù)給n個(gè)數(shù)A1n設(shè)計(jì)在線算法, 對(duì)于詢問(i, j, k), 返回Ai.

20、j第k大元素57分析預(yù)處理：建立線段樹，每個(gè)線段保存該區(qū)間內(nèi)元素排序好的序列查詢處理：任意i,j可分解為最多2logn個(gè)不重疊區(qū)間的并，只需二分W, 每次計(jì)算2logn個(gè)區(qū)間內(nèi)一共有多少個(gè)數(shù)比W大，用logW次時(shí)間可求出第k大元素58分析區(qū)間內(nèi)的數(shù)已排序，用二分每個(gè)區(qū)間求比W大的數(shù)logn累加所有2logn個(gè)區(qū)間比W大的數(shù)，共log2n實(shí)現(xiàn): 一個(gè)歸并排序可以同時(shí)構(gòu)造線段樹和每個(gè)節(jié)點(diǎn)內(nèi)的排序數(shù)組. 時(shí)間: O(logW*log2n)空間:O(nlogn)59例題: 區(qū)間有n個(gè)閉區(qū)間ai,bi，其中i=1,2,n，每一段被涂成黑色整個(gè)數(shù)軸被涂為幾段黑色？60分析按左端點(diǎn)從左到右排序從左到右掃描，

21、若下一個(gè)區(qū)間的左端點(diǎn)分離，則區(qū)間數(shù)加一，否則擴(kuò)展當(dāng)前區(qū)間的右端點(diǎn)時(shí)間復(fù)雜度：O(nlogn)61例題: 輪廓線每一個(gè)建筑物用一個(gè)三元組表示(L, H, R), 表示左邊界, 高度和右邊界輪廓線用X, Y, X, Y這樣的交替式表示右圖的輪廓線為: (1, 11, 3, 13, 9, 0, 12, 7, 16, 3, 19, 18, 22, 3, 23, 13, 29, 0) 給N個(gè)建筑，求輪廓線62分析算法一: 用數(shù)組記錄每一個(gè)元線段的高度離散化, 有n個(gè)元線段每次插入可能影響n個(gè)元線段, O(n), 共O(n2)從左到右掃描元線段高度, 得輪廓線算法二：每個(gè)建筑的左右邊界為事件點(diǎn)把事件點(diǎn)排序

22、, 從左到右掃描維護(hù)建筑物集合, 事件點(diǎn)為線段的插入刪除需要求最高建筑物, 用堆, 共O(nlogn)63思考: 照亮的山景在一片山的上空，高度為T處有N個(gè)處于不同水平位置的燈泡，如果山的邊界上某一點(diǎn)與某燈i的連線不經(jīng)過山上的其他點(diǎn)，我們稱燈i可以照亮該點(diǎn)。開盡量少的燈，使得整個(gè)山景都被照亮。燈的位置固定。一定有解 64思考: 噴水裝置有一塊草坪，長為l，寬為w在它的中心線上裝有n個(gè)點(diǎn)狀的噴水裝置效果是讓以它為中心半徑為ri的圓被潤濕選擇盡量少的噴水裝置把整個(gè)草坪全部潤濕，65例題: 啤酒廠n個(gè)點(diǎn)連成環(huán)狀，每相鄰兩點(diǎn)間有距離值如果選擇其中一個(gè)點(diǎn)建立啤酒廠，則它需要給所有其他城市運(yùn)送啤酒每個(gè)城市

23、都有啤酒需求量di運(yùn)到城市i的費(fèi)用為啤酒廠到i的最小距離乘以di選擇讓總費(fèi)用最小的啤酒廠66分析如果啤酒廠建在s，則所有城市分為兩部分s順時(shí)針方向移動(dòng)時(shí)p也順時(shí)針方向移動(dòng)，處理p移動(dòng)的時(shí)間為O(n)總費(fèi)用的改變量來源于四部分：始終S-的部分，始終為S+的部分，從S-變?yōu)镾+的部分，從S+變?yōu)镾-的部分67例題: 水庫已知有N個(gè)水庫，水庫的當(dāng)前水量為Wi,能夠儲(chǔ)存的容量為Li?，F(xiàn)在可以選擇炸掉其中的某些水庫：一旦炸掉第i個(gè)水庫，那么水庫中的水就會(huì)流到第i+1個(gè)水庫。如果某個(gè)水庫的當(dāng)前水量超過了容量，那么這個(gè)水庫將回倒塌，而所有當(dāng)前的水也會(huì)流到下一個(gè)水庫。炸第i個(gè)水庫需要的費(fèi)用為Ci，現(xiàn)在的目標(biāo)是

24、使第N個(gè)水庫倒塌或者爆炸。68分析設(shè)用炸彈炸的第一個(gè)水庫為第i個(gè)水庫。則顯然第1i-1個(gè)水庫都安然無恙，第i+1n個(gè)水庫要不被炸掉要不被水沖倒塌。（否則費(fèi)用不會(huì)最小）第j個(gè)水庫是否要需要炸掉？這只要看Wi+Wj是否大于Lj即可：設(shè)Si=W1+Wi，則Sj-LjSi-1時(shí)不需要用炸彈，否則需要用炸彈。69分析若我們從大到小的枚舉i，則Si-1是遞減的，也就是說當(dāng)i=k水庫j不需要用炸彈時(shí)，iSi-1的水庫的從堆中刪去。 70例題: 序列反轉(zhuǎn)N個(gè)球按照編號(hào)從1到N排放在桌上。定義一種操作，每次將xy范圍內(nèi)的球，進(jìn)行倒置，就是把它們反過來放。如2 3 7 4變成了4 7 3 2。給定M個(gè)連續(xù)的操作，

25、要求我們給出操作后的序列。71算法一離散化加模擬。初始時(shí)候，只有1.N一個(gè)塊，每次處理一個(gè)操作，會(huì)將一個(gè)塊分成最多三塊，塊的順序適當(dāng)改變，另外每個(gè)塊自身可能被翻轉(zhuǎn)因?yàn)槲覀兓凇皦K”進(jìn)行操作，類似于離散化，每次最多增加2塊，因此總時(shí)間復(fù)雜度為O(M2)。 72算法二首先把這n個(gè)數(shù)分成sqrt(n)段, 每段長度基本相等. 處理時(shí)只要處理首尾兩段就可以了, 中間的段只要記錄當(dāng)前是順序還是逆序時(shí)間復(fù)雜度O(n0.5m)73四、串的算法74字符串字符串: 可變長的字符數(shù)組. 本文中串S的第i個(gè)字符用Si表示, 從第i個(gè)到第j個(gè)字符用Si.j表示實(shí)現(xiàn): 可以在末尾加一個(gè)結(jié)束標(biāo)志, 如0, 也可以記錄字符串的長度基本操作: 取長度, 取指定位置的字符, 取子串, 模式匹配75問題1: 替換連續(xù)空格問題: 把連續(xù)空格改為單個(gè)空格. 例如對(duì)輸入s=There are many spaces., 輸出為There are many spaces.76分析算法一: 每遇到空格就把后面的字符往前移算法二: 用兩個(gè)指針, 讀指針持續(xù)移動(dòng), 當(dāng)遇到第二個(gè)空格時(shí)寫指針不動(dòng).比較: 算法一最壞O(N2)的, 算法二是O(N)的啟發(fā): 字符串問題一般容易設(shè)計(jì)正確的算法, 但需要深入分析才能找到高效算法77問題2: 字符串排序給n個(gè)字符串把它們按字典序從小到大排序78分析和