1-5算法分析v第一章緒論算法分析算法設(shè)計：面對一個問題，如何設(shè)計一個高效的算法算法分析：對已設(shè)計的算法，如何評價或判斷其優(yōu)劣檢驗評估指導(dǎo)改進如何評價算法？易讀性健壯（容錯）性可維護性可擴展性……效率（速度）——算法的核心和靈魂算法分析算法的時間復(fù)雜度學(xué)什么？算法的空間復(fù)雜度算法分析實例1-5-1算法的時間復(fù)雜度v第一章緒論度量算法效率如何度量算法的效率呢？缺點：（1）編寫程序?qū)崿F(xiàn)算法將花費較多的時間和精力

（2）所得實驗結(jié)果依賴于計算機的軟硬件等環(huán)境因素

事后統(tǒng)計（定量分析）：將算法實現(xiàn)，測算其時間和空間開銷事前分析（定性分析）：對算法所消耗資源的一種估算方法時間空間對估算方法有什么要求呢？能夠刻畫效率；與語言環(huán)境無關(guān)；具有一般性……時間復(fù)雜度算法的執(zhí)行時間＝每條語句執(zhí)行時間之和執(zhí)行次數(shù)×執(zhí)行一次的時間指令系統(tǒng)、編譯的代碼質(zhì)量單位時間每條語句執(zhí)行次數(shù)之和=for(i=1;i<=n;i++)for(j=1;j<=n;j++)x++;基本語句的執(zhí)行次數(shù)問題規(guī)模：輸入量的大小基本語句：執(zhí)行次數(shù)與整個算法的執(zhí)行次數(shù)成正比的操作指令注意到，幾乎所有算法，對于規(guī)模更大的輸入需要運行更長的時間運行算法所需要的時間

T

是問題規(guī)模

n

的函數(shù)，記作

T(n)如何表示算法的運行時間函數(shù)呢？算法的運行時間=基本語句的執(zhí)行次數(shù)如何計算算法中基本語句的執(zhí)行次數(shù)呢？時間復(fù)雜度：當(dāng)問題規(guī)模充分大時，算法中基本語句的執(zhí)行次數(shù)在漸近意義下的階——關(guān)注的是增長趨勢問題規(guī)?？梢允嵌鄠€變量

多元函數(shù)時間復(fù)雜度大O記號定義1-1若存在兩個正的常數(shù)

c和

n0，對于任意

n≥n0，都有T(n)≤c×f(n)，則稱T(n)=O(f(n))。n0問題規(guī)模n執(zhí)行次數(shù)n0之前的情況無關(guān)緊要T(n)c×f(n)T(n)和f(n)具有相同的增長趨勢，T(n)的增長至多趨同于函數(shù)f(n)的增長定理1-1：若T(n)=amnm+am-1nm-1+

+a1n+a0是一個m次多項式，則T(n)=O(nm)關(guān)注增長率——忽略所有低次冪和最高次冪的系數(shù)大O記號時間復(fù)雜度是一種估算技術(shù)（信封背面的技術(shù)）Ο(1)＜(log2n)＜(n)＜(nlog2n)＜(n2)＜(n3)＜…＜(2n)＜(n!)常見的時間復(fù)雜度：多項式時間，易解問題指數(shù)時間，難解問題時間復(fù)雜度是在不同數(shù)量級的層面上比較算法大O記號估算的局限冰雹猜想（HailstoneSequence，角谷猜想，3n+1問題）1.輸入一個正整數(shù)n；2.如果n

等于1，結(jié)束算法；3.如果n

是奇數(shù)，則n

變?yōu)?n+1，否則n

變?yōu)閚/2；4.重新執(zhí)行步驟2；所有測試的正整數(shù)都可以終止，但是至今沒有人證明對所有的正整數(shù)該過程都能夠終止，而且至今沒有人能夠分析這個簡單算法的時間復(fù)雜度例如：n=9，有{9,

28,

14,

7,

22,

11,

34,

17,

52,

26,

13,

40,

20,

10,

5,

16,

8,

4,

2,

1}例如：n=27，經(jīng)過77步變換到達頂峰值9232，又經(jīng)過32步變換到達谷底值11-5-2算法的空間復(fù)雜度v第一章緒論空間分析算法在運行過程中需要哪些存儲空間？（1）輸入/輸出數(shù)據(jù)占用的空間取決于問題，與算法無關(guān)intCommonFactor(intm,intn){}voidBubbleSort(intr[],intn){ }voidEquation(doublea,doubleb,doublec,double*p,double*q){}（2）算法本身占用的空間與算法相關(guān)，大小固定intCommonFactor(intm,intn){intr=m%n;while(r!=0){m=n;n=r;r=m%n;}returnn;}（1）輸入/輸出數(shù)據(jù)占用的空間取決于問題，與算法無關(guān)空間分析算法在運行過程中需要哪些存儲空間？（3）執(zhí)行算法需要的輔助空間與算法相關(guān)，體現(xiàn)效率除算法本身和輸入輸出數(shù)據(jù)所占用的空間外，算法臨時開辟的存儲空間空間復(fù)雜度：算法在執(zhí)行過程中需要的輔助空間數(shù)量空間復(fù)雜度也是問題規(guī)模的函數(shù)，通常記作：S(n)=O(f(n))（2）算法本身占用的空間與算法相關(guān)，大小固定（1）輸入/輸出數(shù)據(jù)占用的空間取決于問題，與算法無關(guān)空間分析算法在運行過程中需要哪些存儲空間？空間復(fù)雜度voidBubbleSort(intr[],intn){ intj,temp,bound,exchange=n; while(exchange!=0){

bound=exchange;exchange=0;for(j=1;j<bound;j++)if(r[j]>r[j+1]){temp=r[j];r[j]=r[j+1];r[j+1]=temp;exchange=j;}}}voidMerge(intr[],ints,intm,intt){intr1[n];inti=s,j=m+1,k=s;while(i<=m&&j<=t){if(r[i]<=r[j])r1[k++]=r[i++];elser1[k++]=r[j++];}while(i<=m)r1[k++]=r[i++];while(j<=t)r1[k++]=r[j++];for(i=s;i<t;i++)r[i]=r1[i];}O(1)O(n)就地（原地）算法：空間復(fù)雜度為O(1)，輔助空間是常數(shù)1-5-3算法分析實例v第一章緒論非遞歸算法例1++x;例2for(i=1;i<=n;++i)++x;O(1)常數(shù)階O(n)線性階例3for(i=1;i<=n;++i)for(j=1;j<=n;++j)++x;O(n2)平方階例4for(i=1;i<=n;++i)for(j=1;j<=n;++j){c[i][j]=0;for(k=1;k<=n;++k)c[i][j]+=a[i][k]*b[k][j];}O(n3)立方階例5for(i=1;i<=n;++i)for(j=1;j<=i-1;++j)++x;分析的策略是從內(nèi)部（或最深層部分）向外展開例6for(i=1;i<=n;i=2*i) ++x;O(log2n)對數(shù)階分析的策略是設(shè)其執(zhí)行次數(shù)為T(n)，則有2T(n)≤n，即T(n)≤log2nO(n2)T(n)=O(log2n)=O(logn)非遞歸算法遞歸算法分析的策略是根據(jù)遞歸過程建立遞推關(guān)系式并求解（求和表達式）例7分析遞推式

的時間復(fù)雜度假定

n=2k各種情況基本語句的執(zhí)行次數(shù)是否只和問題規(guī)模有關(guān)？例8在一維整型數(shù)組A[n]中順序查找與給定值k相等的元素

intFind(intA[],intn,intk)

{for(i=0;i<n;i++)if(A[i]==k)break;returni; }如果算法的時間代價與輸入數(shù)據(jù)有關(guān)，則需要分析最好情況、