算法設(shè)計與分析_03算法分析

1、2022-2-19算法設(shè)計與分析演示稿 紀(jì)玉波制作(C)1算法設(shè)計與分析算法設(shè)計與分析問題下界的分析方法問題下界的分析方法2022-2-192 前面已講過，對于一個問題來說，所有能解決此問題的算法中最快的算法的復(fù)雜性，叫做這個問題的復(fù)雜性。所以問題的復(fù)雜性就是此問題所有算法的復(fù)雜性的下界(lower bound），即不會有此問題的算法比下界Tl再快了。凡是一個算法的運算時間等于該問題的Tl，此算法叫做最優(yōu)的算法。 算法的運算時間不僅和問題的規(guī)模n有關(guān)，往往還與具體輸入的數(shù)據(jù)有關(guān)。一般在考慮運算時間時可有兩種考慮辦法：一種辦法是考慮平均情況，即考慮同樣n值時各種可能的輸入，取它們運算時間的平均值

2、；另一種辦法是考慮最壞情況，即考慮各種可能的輸入中運算最慢的一種情況?？紤]平均情況時算法的復(fù)雜性稱為平均復(fù)雜性，考慮最壞情況時算法的復(fù)雜性稱為最壞復(fù)雜性。一般情況下總是考慮最壞的情況，所以不特別說明時，算法的復(fù)雜性是指最壞情況時的復(fù)雜性。研究問題的下界，也是指最壞的輸入情況。2022-2-193問題下界的分析方法 所謂問題的下界，是指某一規(guī)模n的問題在輸入數(shù)據(jù)不利的情況下至少需要多少運算次數(shù)。知道了問題的下界，可以對一個算法進行評價看是否最優(yōu)。下面介紹兩種分析問題下界的方法2022-2-1941. 信息論下界 有很多問題，靠一系列的回答提問即可解決，且每個提問只有“是”或“否”兩種答案。例如對

3、集合x1,xn進行排序的問題，只要回答一系列的“是否xi0 then write(k)end 上述過程包含3個 for語句運算次數(shù)都不超過m次。 nmmxi,0（ xi最大值比下標(biāo)大）2022-2-1912 此算法的復(fù)雜性為O（m），比例1分析的還要小，因為它不是靠多次提問（多次比較）來求得解答的，不必求信息論下界。 設(shè)以集合x1,x4=4，3，0，7為例，下圖為陣列A中數(shù)據(jù)的情況，由此可便于理解此算法。 0 1 2 3 4 5 6 7A30021004（begin for k=0 to m do Ak0; （ 0 0 0 0 0 0 0 0） for i=1 to n do Axi i; （

4、 3 0 0 2 1 0 0 4） for k=0 to m do if Ak0 then write(k) （ 0 3 4 7）end）2022-2-1913例3設(shè)集合x1,xn，試判斷在此集合中是否包含有元素y。 此問題只有用y與各xi逐個比較來判斷，最壞的情況要比較n次。但其可能得到的結(jié)論只有“是”或“否”兩種情況，即M=2，其信息論下界logM=1。此信息論下界之所以不能用，原因在于對應(yīng)此問題構(gòu)成的二分樹并非每個終端結(jié)點對應(yīng)一種解答，而是多個終端結(jié)點得出同一種結(jié)論（肯定的結(jié)論可有多種）。2022-2-19142敵手戰(zhàn)術(shù)敵手戰(zhàn)術(shù)（Adversary Strategy） 假設(shè)程序員P力圖根

5、據(jù)一系列提問來得到問題的解答，而他的一個敵手A控制著輸入數(shù)據(jù)x1,xn，并回答P的提問。A可以在任何時刻改變各xi的數(shù)值以盡量使P不能很快得到結(jié)論，但A改變數(shù)據(jù)同他已經(jīng)回答過的問題不能發(fā)生矛盾。這種情況下，P提問的次數(shù)即為問題的下界。2022-2-1915例4對集合x1, x2,x3進行排序。 假設(shè)最初A選擇x1=1，x2=2，x3=3，P第一次提問“是否x1x2？”，A回答“是”，P第二次提問“是否x2x3？”，A若回答“是”，則P就將得到最后結(jié)論。此時A可以將數(shù)值改為x1=1，x2=3，x3=2，這樣的改變與他第一次的回答并不矛盾。現(xiàn)在A回答“否！”，這樣一來P雖然知道x1和x3都比x2小

6、，但不知道x1和x3誰大，還需要第三次提問“是否x1x3？”，才能最后得出結(jié)論。因此此問題的下界Tl=3，這與信息論下界 是一致的。3! 3log2022-2-1916例5在互不相同的n個數(shù) x1, x2,，xn 中找出最大和最小的數(shù)。 假設(shè)最大數(shù)為xmax,，其余的數(shù)為“中間數(shù)”，我們也是利用一系列提問“是否xixj?”來得出最后解答。在整個過程中，每個數(shù)可能有四種情況，分別用、和E表示。 型：表示此數(shù)尚未與別的數(shù)比較過； 型：表示比所有與它比過的數(shù)都大； 型：表示比所有與它比過的數(shù)都小； E型：表示它至少比某一個數(shù)大又至少比某一個數(shù)小。2022-2-1917 顯然，在初始時各xi均為型，在

7、第一次比較后有一個元素變?yōu)樾?，另一個元素變?yōu)樾汀＠^續(xù)比下去，到最后除xmax為型，xmin為型外，所有中間數(shù)均為E型。任一元素一旦變成了E型就排除了是xmax,和xmin的可能性，以后就不比參加比較了。所以各中間數(shù)的類型變化過程只可能有兩種，即 E或 E 敵手A的戰(zhàn)術(shù)是如何改變元素的數(shù)值以盡量推遲+或-型變成E型，使P的提問次數(shù)盡量的多。在兩個元素進行比較時，因已變成E型的不再參加比較，故共有六種情況。下表列出這六種情況可能得到的比較結(jié)果及敵手A做的選擇?？梢钥闯鯝盡量不選擇兩個元素類型都變化的結(jié)果。（表中P的提問為“是否xixj?”）.2022-2-1918比較后 比較前若答“是”若答“否”xixjxixjxixjA選擇100-+-任一種20+-+E“是”30-E+-“否”4+E+E任一種5-EE-任一種6+-EE+-“否”是否xixj2022-2-1919 由此上分析可知，P將每個0型元素變成+或-型所需的比較次數(shù)至少為 。此外還需要將所有中間數(shù)（共n-2個）由+或-型變成E型。由于A的作對，每比較一次只會有一個元素變成E型，故又需要n-2次比較。因此總共需要的比較次數(shù) ，這就是問題的下界。 此問題可