隱藏信息檢測(cè)與還原技術(shù)-中國(guó)科學(xué)技術(shù)大學(xué)培訓(xùn)資料

1、隱藏信息檢測(cè)與還原技術(shù)-中國(guó)科學(xué)技術(shù)大學(xué)Ch.1 緒論緒論1. 故事：想象自己是神化故事的主人公，你有一張不易懂的地圖，上面描述了一處寶藏的藏寶地點(diǎn)。經(jīng)分析你能確定最有可能的兩個(gè)地點(diǎn)是藏寶地點(diǎn)，但二者相距甚遠(yuǎn)。假設(shè)你如果已到達(dá)其中一處，就立即知道該處是否為藏寶地點(diǎn)。你到達(dá)兩處之一地點(diǎn)及從其中一處到另一處的距離是5天的行程。進(jìn)一步假設(shè)有一條惡龍，每晚光顧寶藏并從中拿走一部分財(cái)寶。假設(shè)你取寶藏的方案有兩種：1.1 引言引言 方案1. 花4天的時(shí)間計(jì)算出準(zhǔn)確的藏寶地點(diǎn)，然后出發(fā)尋寶，一旦出發(fā)不能重新計(jì)算 方案2. 有一個(gè)小精靈告訴你地圖的秘密，但你必須付給他報(bào)酬，相當(dāng)于龍3晚上拿走的財(cái)寶 Prob

2、1.1.1 若忽略可能的冒險(xiǎn)和出發(fā)尋寶的代價(jià)，你是否接受小精靈的幫助？ 顯然，應(yīng)該接受小精靈的幫助，因?yàn)槟阒恍杞o出3晚上被盜竊的財(cái)寶量，否則你將失去4晚被盜財(cái)寶量。 但是，若冒險(xiǎn)，你可能做得更好！1.1 引言引言 設(shè)x是你決定之前當(dāng)日的寶藏價(jià)值，設(shè)y是惡龍每晚盜走的寶藏價(jià)值，并設(shè)x9y 方案1：4天計(jì)算確定地址，行程5天，你得到的寶藏價(jià)值為：x-9y 方案2：3y付給精靈，行程5天失去5y，你得到的寶藏價(jià)值為：x-8y 方案3：投硬幣決定先到一處，失敗后到另一處(冒險(xiǎn)方案) 一次成功所得：x-5y，機(jī)會(huì)1/2 二次成功所得：x-10y，機(jī)會(huì)1/21.1 引言引言期望贏利：期望贏利：x-7.5y

3、2. 意義 該故事告訴我們：當(dāng)一個(gè)算法面臨某種選擇時(shí)，有時(shí)隨機(jī)選擇比耗時(shí)做最優(yōu)選擇更好，尤其是當(dāng)最優(yōu)選擇所花的時(shí)間大于隨機(jī)選擇的平均時(shí)間的時(shí)侯 顯然，概率算法只能是期望的時(shí)間更有效，但它有可能遭受到最壞的可能性。3. 期望時(shí)間和平均時(shí)間的區(qū)別v 確定算法的平均執(zhí)行時(shí)間 輸入規(guī)模一定的所有輸入實(shí)例是等概率出現(xiàn)時(shí)，算法的平均執(zhí)行時(shí)間。v 概率算法的期望執(zhí)行時(shí)間 反復(fù)解同一個(gè)輸入實(shí)例所花的平均執(zhí)行時(shí)間。 因此，對(duì)概率算法可以討論如下兩種期望時(shí)間n 平均的期望時(shí)間：所有輸入實(shí)例上平均的期望執(zhí)行時(shí)間n 最壞的期望時(shí)間：最壞的輸入實(shí)例上的期望執(zhí)行時(shí)間4. 例子n快速排序中的隨機(jī)劃分要求學(xué)生寫(xiě)一算法，由老師

4、給出輸入實(shí)例，按運(yùn)行時(shí)間打分，大部分學(xué)生均不敢用簡(jiǎn)單的劃分，運(yùn)行時(shí)間在1500-2600ms，三個(gè)學(xué)生用概率的方法劃分，運(yùn)行時(shí)間平均為300ms。n8皇后問(wèn)題系統(tǒng)的方法放置皇后(回溯法)較合適，找出所有92個(gè)解 O(2n)，若只找92個(gè)其中的任何一個(gè)解可在線(xiàn)性時(shí)間內(nèi)完成O(n)。 隨機(jī)法：隨機(jī)地放置若干皇后能夠改進(jìn)回溯法，特別是當(dāng)n較大時(shí)n判斷大整數(shù)是否為素?cái)?shù)確定算法無(wú)法在可行的時(shí)間內(nèi)判斷一個(gè)數(shù)百位十進(jìn)制數(shù)是否素?cái)?shù)，否則密碼就不安全。 概率算法將有所作為：若能接受一個(gè)任意小的錯(cuò)誤的概率5. 概率算法的特點(diǎn) (1) 不可再現(xiàn)性 在同一個(gè)輸入實(shí)例上，每次執(zhí)行結(jié)果不盡相同，例如n N-皇后問(wèn)題概率算

5、法運(yùn)行不同次將會(huì)找到不同的正確解n 找一給定合數(shù)的非平凡因子每次運(yùn)行的結(jié)果不盡相同，但確定算法每次運(yùn)行結(jié)果必定相同 (2) 分析困難 要求有概率論，統(tǒng)計(jì)學(xué)和數(shù)論的知識(shí)6. 約定 隨機(jī)函數(shù)uniform：隨機(jī)，均勻，獨(dú)立n 設(shè)a，b為實(shí)數(shù)，ab, uniform(a, b) 返回x，a x b 設(shè)i，j為整數(shù)，ij, uniform(i, j)=k, i k j 設(shè)X是非空有限集， uniform(X) X 例1：設(shè)p是一個(gè)素?cái)?shù)，a是一個(gè)整數(shù)滿(mǎn)足1a0 do if (j is odd) s sa mod p;a a2 mod p;j j div 2;return s;Draw (a, p) /

6、在X中隨機(jī)取一元素j uniform(1.p-1);return ModularExponent(a, j, p); / 在X中隨機(jī)取一元素n 偽隨機(jī)數(shù)發(fā)生器在實(shí)用中不可能有真正的隨機(jī)數(shù)發(fā)生器，多數(shù)情況下是用偽隨機(jī)數(shù)發(fā)生器代替。大多數(shù)偽隨機(jī)數(shù)發(fā)生器是基于一對(duì)函數(shù)：S: X X, 這里X足夠大，它是種子的值域R: X Y, Y是偽隨機(jī)數(shù)函數(shù)的值域使用S獲得種子序列：x0=g, xi=S(xi-1), i0然后使用R獲得偽隨機(jī)序列：yi=R(xi), i 0該序列必然是周期性的，但只要S和R選的合適，該周期長(zhǎng)度會(huì)非常長(zhǎng)。TC中可用rand()和srand(time), 用GNU C更好n 基本特征

7、隨機(jī)決策在同一實(shí)例上執(zhí)行兩次其結(jié)果可能不同在同一實(shí)例上執(zhí)行兩次的時(shí)間亦可能不太相同n 分類(lèi)Numerical, Monte Carlo, Las Vegas, Sherwood.很多人將所有概率算法(尤其是數(shù)字的概率算法)稱(chēng)為Monte Carlo算法1.2 概率算法的分類(lèi)概率算法的分類(lèi)n 數(shù)字算法隨機(jī)性被最早用于求數(shù)字問(wèn)題的近似解例如，求一個(gè)系統(tǒng)中隊(duì)列的平均長(zhǎng)度的問(wèn)題，確定算法很難得到答案概率算法獲得的答案一般是近似的，但通常算法執(zhí)行的時(shí)間越長(zhǎng)，精度就越高，誤差就越小使用的理由 現(xiàn)實(shí)世界中的問(wèn)題在原理上可能就不存在精確解例如，實(shí)驗(yàn)數(shù)據(jù)本身就是近似的，一個(gè)無(wú)理數(shù)在計(jì)算機(jī)中只能近似地表示 精確解

8、存在但無(wú)法在可行的時(shí)間內(nèi)求得有時(shí)答案是以置信區(qū)間的形式給出的1.2 概率算法的分類(lèi)概率算法的分類(lèi)n Monte Carlo算法 (MC算法)蒙特卡洛算法1945年由J. Von Neumann進(jìn)行核武模擬提出的。它是以概率和統(tǒng)計(jì)的理論與方法為基礎(chǔ)的一種數(shù)值計(jì)算方法，它是雙重近似：一是用概率模型模擬近似的數(shù)值計(jì)算，二是用偽隨機(jī)數(shù)模擬真正的隨機(jī)變量的樣本。這里我們指的MC算法是： 若問(wèn)題只有1個(gè)正確的解，而無(wú)近似解的可能時(shí)使用MC算法例如，判定問(wèn)題只有真或假兩種可能性，沒(méi)有近似解 因式分解，我們不能說(shuō)某數(shù)幾乎是一個(gè)因子n 特點(diǎn)：MC算法總是給出一個(gè)答案，但該答案未必正確，成功(即答案是正確的)的概

9、率正比于算法執(zhí)行的時(shí)間n 缺點(diǎn)：一般不能有效地確定算法的答案是否正確1.2 概率算法的分類(lèi)概率算法的分類(lèi)n Las Vegas算法 (LV算法)LV算法絕不返回錯(cuò)誤的答案。n 特點(diǎn)：獲得的答案必定正確，但有時(shí)它仍根本就找不到答案。 和MC算法一樣，成功的概率亦隨算法執(zhí)行時(shí)間增加而增加。無(wú)論輸入何種實(shí)例，只要算法在該實(shí)例上運(yùn)行足夠的次數(shù)，則算法失敗的概率就任意小。 Sherwood算法Sherwood算法總是給出正確的答案。當(dāng)某些確定算法解決一個(gè)特殊問(wèn)題平均的時(shí)間比最壞時(shí)間快得多時(shí)，我們可以使用Sherwood算法來(lái)減少，甚至是消除好的和壞的實(shí)例之間的差別。1.2 概率算法的分類(lèi)概率算法的分類(lèi)這

10、類(lèi)算法主要用于找到一個(gè)數(shù)字問(wèn)題的近似解2.1 值計(jì)算n實(shí)驗(yàn)：將n根飛鏢隨機(jī)投向一正方形的靶子，計(jì)算落入此正方形的內(nèi)切圓中的飛鏢數(shù)目k。假定飛鏢擊中方形靶子任一點(diǎn)的概率相等(用計(jì)算機(jī)模擬比任一飛鏢高手更能保證此假設(shè)成立)設(shè)圓的半徑為r，面積s1= r2； 方靶面積s2=4r2由等概率假設(shè)可知落入圓中的飛鏢和正方形內(nèi)的飛鏢平均比為：由此知： Ch.2 數(shù)字概率算法數(shù)字概率算法2244krnr4 /4nk n kn求近似值的算法為簡(jiǎn)單起見(jiàn)，只以上圖的右上1/4象限為樣本Darts (n) k 0;for i 1 to n do x uniform(0, 1);y uniform(0, 1); / 隨

11、機(jī)產(chǎn)生點(diǎn)(x,y)if (x2 + y2 1) then k+; /圓內(nèi)return 4k/n;實(shí)驗(yàn)結(jié)果： =3.141592654n = 1000萬(wàn): 3.140740, 3.142568 (2位精確)n = 1億: 3.141691, 3.141363 (3位精確)n = 10億: 3.141527, 3.141507 (4位精確)2.1 值計(jì)算值計(jì)算n 求近似值的算法Ex.1 若將y uniform(0, 1) 改為 y x, 則上述的算法估計(jì)的值是什么？2.1 值計(jì)算值計(jì)算Monte Carlo積分(但不是指我們定義的MC算法)n概率算法1設(shè)f: 0, 1 0, 1是一個(gè)連續(xù)函數(shù)，則由

12、曲線(xiàn)y=f(x), x軸, y軸和直線(xiàn)x=1圍成的面積由下述積分給出：向單位面積的正方形內(nèi)投鏢n次，落入陰影部分的鏢的數(shù)目為k，則顯然，只要n足夠大2.2 數(shù)字積分?jǐn)?shù)字積分 (計(jì)算定積分的值計(jì)算定積分的值)10( )Sf x dx/1kSSk nn/Sk n n概率算法1HitorMiss (f, n) k 0;for i 1 to n do x uniform(0, 1);y uniform(0, 1);if y f(x) then k+;return k/n;Note: 是S/4的面積， =S, 2.2 數(shù)字積分?jǐn)?shù)字積分 (計(jì)算定積分的值計(jì)算定積分的值)1201x dx12041x dxn

13、 概率算法1Ex2. 在機(jī)器上用 估計(jì)值，給出不同的n值及精度。Ex3. 設(shè)a, b, c和d是實(shí)數(shù)，且a b, c d, f:a, b c, d是一個(gè)連續(xù)函數(shù)，寫(xiě)一概率算法計(jì)算積分：注意，函數(shù)的參數(shù)是a, b, c, d, n和f, 其中f用函數(shù)指針實(shí)現(xiàn)，請(qǐng)選一連續(xù)函數(shù)做實(shí)驗(yàn)，并給出實(shí)驗(yàn)結(jié)果。2.2 數(shù)字積分?jǐn)?shù)字積分 (計(jì)算定積分的值計(jì)算定積分的值)12041x dx( )baf x dxn概率算法1*Ex4. 設(shè),是(0,1)之間的常數(shù)，證明：若I是 的正確值，h是由HitorHiss算法返回的值，則當(dāng)n I(1-I)/2時(shí)有：Prob|h-I| 1 上述的意義告訴我們：Prob|h-I|

14、 , 即：當(dāng)n I(1-I)/ 2時(shí)，算法的計(jì)算結(jié)果的絕對(duì)誤差超過(guò)的概率不超過(guò)，因此我們根據(jù)給定和可以確定算法迭代的次數(shù)解此問(wèn)題時(shí)可用切比雪夫不等式，將I看作是數(shù)學(xué)期望。2.2 數(shù)字積分?jǐn)?shù)字積分 (計(jì)算定積分的值計(jì)算定積分的值)10( )f x dx22(1)11(1)44IInII n概率算法2更有效的概率算法是： 在積分區(qū)間上隨機(jī)均勻地產(chǎn)生點(diǎn)，求出這些點(diǎn)上的函數(shù)值的算術(shù)平均值，再乘以區(qū)間的寬度：Crude (f, n, a, b) sum 0;for i 1 to n do x uniform(a, b);sum sum + f(x);return (b-a)sum/n;2.2 數(shù)字積分?jǐn)?shù)

15、字積分 (計(jì)算定積分的值計(jì)算定積分的值)11( )()( ),nbiiaif x dxbaf xaxbnn 概率算法2用HitorMiss和Crude運(yùn)行三次的結(jié)果為：假定 和 存在，由算法求得的估算值的方差反比于點(diǎn)數(shù)n。當(dāng)n足夠大時(shí)，估計(jì)的分布近似為正態(tài)分布。對(duì)于給定的迭代次數(shù)n，Crude算法的方差不會(huì)大于HitorMiss的方差。但不能說(shuō)，Crude算法總是優(yōu)于HitorMiss。因?yàn)楹笳咴诮o定的時(shí)間內(nèi)能迭代的次數(shù)更多。例如，計(jì)算值時(shí)，Crude需計(jì)算平方根，而用投鏢算法darts時(shí)無(wú)需計(jì)算平方根。2.2 數(shù)字積分?jǐn)?shù)字積分 (計(jì)算定積分的值計(jì)算定積分的值)3.141855, 3.1414

16、22, 3.14143413.141662,3.141486, 3.141527hitncrude億( )baf x dx2( )bafx dxn確定的算法梯形算法將區(qū)間分為n-1個(gè)子區(qū)間，每個(gè)子區(qū)間內(nèi)的長(zhǎng)度為，Trapezoid (f, n, a, b) / 假設(shè) n 2delta (b-a)/(n-1);sum (f(a) + f(b)/2;for x a+delta step delta to b delta dosum sum + f(x)return sum delta;2.2 數(shù)字積分?jǐn)?shù)字積分 (計(jì)算定積分的值計(jì)算定積分的值)f(a)f(b)=f af a 22積分值( ( + )

17、+ ( +)+.+)n確定的算法 當(dāng)n=100, =3.140399 當(dāng)n=1,000, =3.141555 當(dāng)n=10,000, =3.141586 當(dāng)n=100,000, =3.141593一般地，在同樣的精度下，梯形算法的迭代次數(shù)少于MC積分，但是n 有時(shí)確定型積分算法求不出解：例如， f(x)=sin2(100)! x)， 。 但是用梯形算法時(shí)，當(dāng)2 n101時(shí)，返回值是0。若用MC積分則不會(huì)發(fā)生該類(lèi)問(wèn)題，或雖然發(fā)生，但概率小得多。2.2 數(shù)字積分?jǐn)?shù)字積分 (計(jì)算定積分的值計(jì)算定積分的值)101( )2f x dx n 多重積分 在確定算法中，為了達(dá)到一定的精度，采樣點(diǎn)的數(shù)目隨著積分維

18、數(shù)成指數(shù)增長(zhǎng)，例如，一維積分若有100個(gè)點(diǎn)可達(dá)到一定的精度，則二維積分可能要計(jì)算1002個(gè)點(diǎn)才能達(dá)到同樣的精度，三維積分則需計(jì)算1003個(gè)點(diǎn)。(系統(tǒng)的方法) 但概率算法對(duì)維數(shù)的敏感度不大，僅是每次迭代中計(jì)算的量稍增一點(diǎn)，實(shí)際上，MC積分特別適合用于計(jì)算4或更高維數(shù)的定積分。 若要提高精度，則可用混合技術(shù)：部分采用系統(tǒng)的方法，部分采用概率的方法2.2 數(shù)字積分?jǐn)?shù)字積分 (計(jì)算定積分的值計(jì)算定積分的值) 上一節(jié)可以認(rèn)為，數(shù)字概率算法被用來(lái)近似一個(gè)實(shí)數(shù)，本節(jié)可用它們來(lái)估計(jì)一個(gè)整數(shù)值。例如，設(shè)X為有限集，若要求X的勢(shì)|X|，則當(dāng)X較大時(shí)，枚舉顯然不現(xiàn)實(shí)。n 問(wèn)題：隨機(jī)選出25人，你是否愿意賭其中至少有

19、兩個(gè)人生日相同嗎？直覺(jué)告訴我們，一般人都不愿意賭其成立，但實(shí)際上成立的概率大于50%。2.3 概率計(jì)數(shù)概率計(jì)數(shù) 一般地，從n個(gè)對(duì)象中選出k個(gè)互不相同的對(duì)象，若考慮 選擇的次序，則不同的選擇有 種；若允許重復(fù)選取同 一對(duì)象，則不同的選法共有 種。 因此，從n個(gè)對(duì)象(允許同一對(duì)象重復(fù)取多次)中隨機(jī)均勻地選擇出的k個(gè)對(duì)象互不相同的概率是： ，注意a，b和b，a是不同的取法。由此可知，上述問(wèn)題中，25個(gè)人生日互不相同的概率是：這里假設(shè)：不考慮潤(rùn)年，一年中人的生日是均勻分布的。2.3 概率計(jì)數(shù)概率計(jì)數(shù)!()!nnkkn!()!knnkn25365!365,25340!365nk由Stirling公式知：

20、可得 假定 Tj;3.2 隨機(jī)的預(yù)處理隨機(jī)的預(yù)處理例2：離散對(duì)數(shù)計(jì)算離散對(duì)數(shù)計(jì)算困難使其可用于密碼算法，數(shù)字簽名等定義：設(shè) a=gx mod p， 記 logg,pa=x，稱(chēng)x為a的(以g為底模除p)對(duì)數(shù)從p，g，a計(jì)算x稱(chēng)為離散對(duì)數(shù)問(wèn)題。簡(jiǎn)單算法： 計(jì)算gx對(duì)所有的x，最多計(jì)算0 x p-1 或 1xp，因?yàn)閷?shí)際上離散對(duì)數(shù)是循環(huán)群； 驗(yàn)證a=gx mod p 是否成立。dlog(g, a, p) / 當(dāng)這樣的對(duì)數(shù)不存在時(shí)，算法返回p x 0; y 1; do x+; y y*g; / 計(jì)算y=gx while ( a y mod p) and (x p); return x3.2 隨機(jī)的預(yù)處

21、理隨機(jī)的預(yù)處理2,7xlog3x32 mod7例無(wú)解，不存在使問(wèn)題：最壞O(p)循環(huán)次數(shù)難以預(yù)料，當(dāng)滿(mǎn)足一定條件時(shí)平均循環(huán)p/2次當(dāng)p=24位十進(jìn)制數(shù)，循環(huán)1024次，千萬(wàn)億次/秒 (1016次/秒) 大約算1年(108秒/年)若p是數(shù)百位十進(jìn)制？隨機(jī)選擇都可能無(wú)法在可行的時(shí)間內(nèi)求解。假設(shè)有一個(gè)平均時(shí)間性能很好，但最壞情況差的確定算法求logp,ga，怎樣用Sherwood算法求解該問(wèn)題？設(shè)p=19, g=2當(dāng)a=14, 6時(shí)，log2,1914 = 7, log2,196=14，即用dlog求14和6的離散對(duì)數(shù)時(shí)，分別要循環(huán)7和14次，執(zhí)行時(shí)間與a的取值相關(guān)。 用sherwood算法應(yīng)該使得

22、與a無(wú)關(guān)，用隨機(jī)預(yù)處理的方法計(jì)算logg,pa3.2 隨機(jī)的預(yù)處理隨機(jī)的預(yù)處理定理(見(jiàn)p877, 31.6) dlogRH(g, a p) / 求logg,pa, a = gx mod p，求x / Sherwood算法 r uniform(0.p-2); b ModularExponent(g, r, p); /求冪模b=gr mod p c ba mod p; /(gr modp)(gxmodp)modp=gr+xmodp=c y logg,pc; / 使用確定性算法求logp,gc, y=r+x return (y-r) mod (p-1); / 求xEx. 分析dlogRH的工作原理，

23、指出該算法相應(yīng)的u和v3.2 隨機(jī)的預(yù)處理隨機(jī)的預(yù)處理,log(mod)(loglog)mod(1)log(mod)for 02g pg pg prg pstpstpgprrp隨機(jī)預(yù)處理提供了一種加密計(jì)算的可能性 假定你想計(jì)算某個(gè)實(shí)例x，通過(guò)f(x)計(jì)算，但你缺乏計(jì)算能力或是缺乏有效算法，而別人有相應(yīng)的計(jì)算能力，愿意為你計(jì)算(可能會(huì)收費(fèi))，若你愿意別人幫你計(jì)算，但你不愿意泄露你的輸入實(shí)例x，你將如何做？可將隨機(jī)預(yù)處理使用到f的計(jì)算上： 使用函數(shù)u將x加密為某一隨機(jī)實(shí)例y 將y提交給f計(jì)算出f(y)的值 使用函數(shù)v轉(zhuǎn)換為f(x) 上述過(guò)程，他人除了知道你的實(shí)例大小外，不知道x的任何信息，因?yàn)閡(

24、x,r)的概率分布(只要r是隨機(jī)均勻選擇的)是獨(dú)立于x的。3.2 隨機(jī)的預(yù)處理隨機(jī)的預(yù)處理 設(shè)兩個(gè)數(shù)組val1.n和ptr1.n及head構(gòu)成一個(gè)有序的靜態(tài)鏈表：valhead valptrhead valptrptrhead valptrn-1head例：3.3 搜索有序表搜索有序表:ptri給個(gè)關(guān)鍵標(biāo)非關(guān)鍵即關(guān)鍵出出下下一一字字的的下下if vali最if vali最大大字字0 if vali是0 if vali是最最大大字字 i 1 2 3 4 5 6 7vali 2 3 13 1 5 21 8ptri 2 5 6 1 7 0 3rank 2 3 6 1 4 7 5head=4 有序表：

25、有序表：1，2，3，5，8，13，21 n折半查找： 若val1.n本身有序，可用折半查找找某個(gè)給定的key，時(shí)間為O(lgn)。n順序查找：但此表為鏈?zhǔn)浇Y(jié)構(gòu)，故最壞時(shí)間是(n)。盡管如此，我們能夠找到一個(gè)確定性算法，平均時(shí)間為 。 相應(yīng)的Sherwood算法的期望時(shí)間是 ，它雖然并不比確定性算法快，但他消除了最壞實(shí)例。 假定表中元素互不相同，且所求的關(guān)鍵字在表中存在，則給定x，我們是求下標(biāo)i，使vali=x, 這里1i n。任何實(shí)例可以由兩個(gè)參數(shù)刻畫(huà)： 前n個(gè)整數(shù)的排列 x的rank3.3 搜索有序表搜索有序表()On()On設(shè)Sn是所有n!個(gè)排列的集合，設(shè)A是一個(gè)確定性算法 tA(n, k

26、, )表示算法A的執(zhí)行時(shí)間，此時(shí)間與被查找元素的秩k，以及val的排列相關(guān)。若A是一個(gè)概率算法，則tA(n, k, )表示算法的期望值。無(wú)論算法是確定的還是概率的，wA(n)和mA(n)分別表示最壞時(shí)間和平均時(shí)間，因此有： 3.3 搜索有序表搜索有序表1( )max ( , , )|1 1( )( , , )!11,2,.,1/!nAnnAASknw nt n kkn andSm ntn kn nknnSn的概率是，在 中每個(gè)排列的概率是時(shí)間為O(n)的確定算法n算法 設(shè)xvali且x在表中，則從位置i開(kāi)始查找x的算法為：Search(x, i) /仍可改進(jìn)while x vali do i

27、ptri;return i;在表val1.n中查找x的算法為：A(x) return Search(x, head);3.3 搜索有序表搜索有序表n 性能分析設(shè)rank(x)=k, 則： 算法A在n個(gè)元素的表中查找x所需的訪(fǎng)問(wèn)數(shù)組元素的次數(shù)，顯然與無(wú)關(guān) 算法A最壞時(shí)的訪(fǎng)問(wèn)次數(shù) 算法A平均的訪(fǎng)問(wèn)次數(shù) 3.3 搜索有序表搜索有序表( , )Atn kw ( )Anm ( )An1,1, ,( , ),( ),1,2,.,11( )( , )2( )( )AAnAAknNkn tn kknNknwnnnNknnmntn knT nO n 若時(shí)為最壞情況，此時(shí)設(shè)的概率相等，則綜上所述，時(shí)間為O(n)的

28、概率算法n算法 D(x) i uniform(1.n);y vali;case x y: return Search(x, ptri); / case2 otherwise: return i; / case3， x = y3.3 搜索有序表搜索有序表n性能分析(D訪(fǎng)問(wèn)數(shù)組次數(shù)) 一般情況 設(shè)rank(x)=k, rank(vali)=j 若 k j, 則 ，屬于case2，從jth最小元之后搜索若 k = j, 則 ，屬于case3 最壞情況3.3 搜索有序表搜索有序表( , ) Dtn kk( , )-Dtn kkj( , )0Dtn kDDnN,w (n)?j 1,knSearchn-1w (n)n 1 當(dāng)時(shí)，執(zhí)行次數(shù)為， 平均情況3.3 搜索有序表搜索有序表121111121,( )?11,2,.,1,2,.,11( )( , )()1(1)(1)()11()22333 DjnnnnDDjkjkkjnjnN mnjnknnmntn kkkjnn