1、算法是正確的嗎？算法是正確的嗎？算法的模擬與分析算法的模擬與分析1.算法正確嗎？算法正確嗎？ 問題求解過程、方法正確嗎？輸出的是不是問題的解？問題求解過程、方法正確嗎？輸出的是不是問題的解？ 20世紀(jì)世紀(jì)60年代，美國一架發(fā)往金星的航天飛機由于控制程年代，美國一架發(fā)往金星的航天飛機由于控制程序出錯而永久丟失在太空中。序出錯而永久丟失在太空中。算法獲得的解是最優(yōu)的嗎？算法獲得的解是最優(yōu)的嗎？算法的效果評價算法的效果評價 算法輸出的是最優(yōu)解還是可行解？如果是可行解，與最優(yōu)解算法輸出的是最優(yōu)解還是可行解？如果是可行解，與最優(yōu)解的偏差多大？的偏差多大？ 證明：（證明：（1）利用數(shù)學(xué)方法）利用數(shù)學(xué)方法

2、（2）仿真模擬分析）仿真模擬分析算法的復(fù)雜性分析算法的復(fù)雜性分析算法的復(fù)雜性評價方面：時間，空間算法的復(fù)雜性評價方面：時間，空間 時間時間復(fù)雜度是指執(zhí)行算法所需要的計算工作量；而空間復(fù)雜度是指執(zhí)行這個算法所需要的內(nèi)復(fù)雜度是指執(zhí)行算法所需要的計算工作量；而空間復(fù)雜度是指執(zhí)行這個算法所需要的內(nèi)存空間。存空間。時間復(fù)雜性時間復(fù)雜性 時間時間復(fù)雜度的定義復(fù)雜度的定義 一般情況下，算法中基本操作一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)重復(fù)執(zhí)行的次數(shù)是問題規(guī)模是問題規(guī)模n的某個函數(shù)，用的某個函數(shù)，用T(n)表示，若有表示，若有某個輔助函數(shù)某個輔助函數(shù)f(n)，使得當(dāng)，使得當(dāng)n趨近于無窮大時，趨近于無窮大時

3、，T(n)/f(n)的極限值為不等于零的常數(shù)，則稱的極限值為不等于零的常數(shù)，則稱f(n)是是T(n)的同數(shù)量級函數(shù)。記作的同數(shù)量級函數(shù)。記作T(n)=O(f(n)，稱，稱O(f(n)為算法的漸進(jìn)時間復(fù)雜度為算法的漸進(jìn)時間復(fù)雜度(O是數(shù)量級的是數(shù)量級的符號符號 )，簡稱時間復(fù)雜度。，簡稱時間復(fù)雜度。通常通常只考慮三種情況下的時間復(fù)雜度，只考慮三種情況下的時間復(fù)雜度，即最壞情況、最好即最壞情況、最好情況情況和平均情況和平均情況下的時間復(fù)雜度，分別記為下的時間復(fù)雜度，分別記為T max (N)、T min (N) 和和T avg (N)，實踐表明可操作性最好且最有實際價值的，實踐表明可操作性最好且最

4、有實際價值的是是最壞情況最壞情況下的下的時間復(fù)雜度。時間復(fù)雜度。示例 在在pascal中比較容易理解，容易計算的方法是：看看有幾重中比較容易理解，容易計算的方法是：看看有幾重for循環(huán)，只有一循環(huán)，只有一重則時間復(fù)雜度為重則時間復(fù)雜度為O(n)，二重則為，二重則為O(n2)，依此類推，如果有二分則為，依此類推，如果有二分則為O(logn)，二，二分例如快速冪、二分查找，如果一個分例如快速冪、二分查找，如果一個for循環(huán)套一個二分，那么時間復(fù)雜度則為循環(huán)套一個二分，那么時間復(fù)雜度則為O(nlogn)。分析分析：1.語句語句int num1, num2;的頻度為的頻度為1；語句語句i=0;的頻度為

5、的頻度為1；語句語句in; i+; num1+=1; j=1; 的頻度為的頻度為n；語句語句j=n; j*=2; num2+=num1;的頻度為的頻度為n*log2n；T(n) = 2 + 4n + 3n*log2n2.忽略掉忽略掉T(n)中的常量、低次冪和最高次冪的系數(shù)中的常量、低次冪和最高次冪的系數(shù)f(n) = n*log2n3.lim(T(n)/f(n) = (2+4n+3n*log2n) / (n*log2n) = 2*(1/n)*(1/log2n) + 4*(1/log2n) + 3當(dāng)當(dāng)n趨向于無窮大，趨向于無窮大，1/n趨向于趨向于0，1/log2n趨向于趨向于0所以極限等于所以極

6、限等于3。T(n) = O(n*log2n)1) 加法規(guī)則加法規(guī)則 T(n,m) = T1(n) + T2(n) = O (max ( f(n), g(m) )2) 乘法規(guī)則乘法規(guī)則 T(n,m) = T1(n) * T2(m) = O (f(n) * g(m)3) 一個特例（問題規(guī)模為常量的時間復(fù)雜度）一個特例（問題規(guī)模為常量的時間復(fù)雜度） 在大在大O表示法里面有一個特例，如果表示法里面有一個特例，如果T1(n) O(c)， c是一個與是一個與n無關(guān)的任意常數(shù)，無關(guān)的任意常數(shù)，T2(n) = O ( f(n) ) 則有則有T(n) = T1(n) * T2(n) = O ( c*f(n) ) = O( f(n) )也就是說也就是說，在大，在大O表示法中，任何非表示法中，任何非0正常數(shù)都屬于同一數(shù)量級，記為正常數(shù)都屬于同一數(shù)量級，記為O(1)。貪心算法（又稱貪婪算法）是指，在對問題求解時，總是做出在當(dāng)前看貪心算法（又稱貪婪算法）是指，在對問題求解時，總是做出在當(dāng)前看來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，他所做出的是來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，他所做出的是在某種意義上的局部最優(yōu)解。在某種意義上的局部最優(yōu)解。貪心算法不是對所有問題都能得到整體最優(yōu)解，關(guān)鍵是貪心策略的選擇，貪心算法不是對所有問題都能