事前分析估算的方法

1、事前分析估算的方法假設(shè)給定的是一臺(tái)通用計(jì)算機(jī)，滿足：口執(zhí)行一條基本語句或一個(gè)基本運(yùn)算需花一個(gè)單位時(shí)間口基本語句指：賦值語句、輸入語句、輸出語句口基本運(yùn)算指：算術(shù)運(yùn)算、一次比較(字符比較、數(shù)值比較)做法：從算法中選取一種對(duì)于所研究的問題(或算法類型)來說是基本操作的原操作，以 該基本操作重復(fù)執(zhí)行的次數(shù)作為算法的時(shí)間量度。例8-1兩個(gè)NXN矩陣A和B相乘的算法。for (i=0;in;i+)for (j=0;jn;j+)cij=0;for (k=0;kn0時(shí)都 滿足|xn|Mfn)|；(換句話就是說，這當(dāng)整型自變量n趨向于無窮大時(shí)，兩者的比值是一個(gè) 不等于0的常數(shù)。)例8-2 NXN矩陣相乘的算法

2、的時(shí)間復(fù)雜度：基本操作執(zhí)行的次數(shù)：nXnXn=n3. T(n)=O(n3)口語句的頻度：是指該語句重復(fù)執(zhí)行的次數(shù)。與該語句包含的基本操作執(zhí)行的次數(shù)相同。例8分析語句+x; s=0;的頻度。解：將+x”看成是基本操作，則語句頻度為1，即時(shí)間復(fù)雜度為。(1)；如果將“s=0”也看 成是基本操作，則語句頻度為2,其時(shí)間復(fù)雜度仍為0(1)，即常量階。例 9 分析語句 for (i=1; i=n; +i)+x; s+=x;解：語句頻度為：2n，其時(shí)間復(fù)雜度為：T(n)=O(n)。即時(shí)間復(fù)雜度為線性階。例 10 分析語句 for (i=1; i=n; +i)for (j=1; j=n; +j)+x; s+

3、=x;解：語句頻度為：2n2,其時(shí)間復(fù)雜度為：O(n2)。即時(shí)間復(fù)雜度為平方階。口 定理：若 A(n)=amnm +am1nm-1 +a1n+a0 是一個(gè) m 次多項(xiàng)式，則 A(n)=O(n m)。(證明 略)m例 11 for (i=2; i=n; +i)for (j=2; j= (y + 1)(y + 1)(y+;以下六種計(jì)算算法時(shí)間復(fù)雜度的多項(xiàng)式是最常用的。其關(guān)系為：O(1)O(logn)O(n)O(nlogn)O(n2)O(n3)指數(shù)時(shí)間的關(guān)系為：O(2n)O(n!)1 & change;-i)(change=false;for(j=0;jaj+1) aj-aj+1;change=TU

4、RE分析：口問題的輸入規(guī)模：n；口基本操作：“交換序列中相鄰兩個(gè)整數(shù)”；實(shí)例：5 1 9 7 3 23 1 2 5 9 7口 “基本操作”數(shù)隨n變化的規(guī)律：-a中序列自小至大有序時(shí)，“基本操作”數(shù)為0；-a中序列自大至小有序時(shí)，“基本操作”數(shù)為=(1+2+3+.+(n-1)=n(n-1)/2口 算法的時(shí)間復(fù)雜度：-最好情況下的時(shí)間復(fù)雜度：0-最壞情況下的時(shí)間復(fù)雜度：W(n) =n(n-1)/2-平均情況下的時(shí)間復(fù)雜度：AV(n) = 1/n!0+1+2+n(n-1)/2=O(n2)總結(jié)：確定算法問題規(guī)模；找出基本操作；分析基本操作是否只依賴于問題規(guī)模？口是，就直接建立基本操作執(zhí)行次數(shù)的求和表達(dá)式，并求解、用漸進(jìn)符號(hào)表示;口否則，分別對(duì)該算法的最好、最壞和平均情況的時(shí)間復(fù)雜度進(jìn)行分析?？谒惴ǖ拇鎯?chǔ)空間代價(jià) 一個(gè)算法的空間效