程序算法的正確性和效率
1、算法的正確性判定
研究計算機算法的目的是為了有效地求出問題的解，用計算機語言描述的算法要在計算機上運行，這引出了對算法效率的分析和討論。例如在象棋比賽中，對任意給出的一種棋局，可以設計一種算法判斷這一棋局的輸贏，算法需要從開局起對所有棋子可能進行的移動、移動前后的每一對策作檢查，做出應走的棋步。計算步驟是有窮的，但在計算機上運算這一算法需要很長的時間。這就說明計算機只能運行在有窮步內終止的算法。 設計出算法后，應證明該算法對所有可能的合法輸入都能計算出正確的結果，這一工作稱為算法確認。算法確認與描述實現這一算法的手段無關，例如可以用不同計算機語言來實現這一算法。用算法語言描述構成的程序在計算機上運行，也應證明該程序是正確的，這一工作稱為程序證明。 對程序的測試包括調試和作時空分布圖。調試程序是在抽象數據集上執行程序，確定是否會產生錯誤的結果，如果出現錯誤，進行修改，再做測試。調試只能指出程序有錯誤，而不能指出程序不存在錯誤。程序的正確性證明是計算機科學一個重要的研究領域。作時空分布圖是用各種給定的測試數據，去調試已經證明是正確的程序，測定一個算法得出運算結果所用去的時間和空間，給出時空分布圖，驗證對算法所作的分析是否正確，找出算法最優化的有效邏輯位置，優化算法的效率。
2、算法的最優性
求解一個問題，如果規定了算法所允許的運算類型，則所有可能的算法構成了解決這個問題的一個算法類，判斷一個算法是否最優的依據，是該算法的平均性態分析。若在選擇的算法類中，如果一個算法比所有的算法執行的基本運算少，此算法應該是最優的。 判斷一個算法是否最優，并不需要對算法類中的每一個算法逐個進行分析，可以根據這個算法類的特性，確定所需運算次數的下界，在算法類中所有運算次數等于這個下界的算法是最優的，這也說明最優算法不是惟一的。需要做兩件工作確定解決一個問題至少需要多少次運算：① 設計一個有效率的算法a，分析a并找到一個函數f，使對尺度為n的輸入，a最多做f(n)次基本運算；② 對某一函數g，證明一個定理，表明對所考慮的算法類中的任何一個算法，存在一個尺度為n的輸入，使算法至少要做g(n)次基本運算。 若函數f與g相等，則算法a是最優的；若不相等，則可能存在一個更好的算法或更好的下界。
3、分析算法
（1） 分析算法的兩個主要內容 要分析一個算法首先要確定使用哪些算法以及執行這些算法所用的時間。運算可以分為兩類，一類是基本運算，包括加、減、乘、除四種基本的整數算術運算以及浮點算術、比較、對變量賦值和過程調用等。這些運算所用的時間不同，但都是花費一個固定量的時間。另一類運算由一些基本運算的任意長序列組成，以兩個字符串的比較運算為例，可以看做是一系列字符比較指令運算，而字符比較指令可以使用移位和位比較指令。比較兩個字符的運算時間是固定的，是某一個常數值，而比較兩個字符串的運算時間值則與字符串的長度相關。 其次是確定能反映出算法在各種情況下工作的測試數據集，設計和編制出能夠產生最優、最差運算結果的輸入數據配置，這些數據配置能夠代表可能出現的典型情況。數據配置的設計是創造性的工作，應能最大限度地適應算法，反映算法運行的環境和功能要求。 （2） 分析算法的兩個階段 對一個算法作出分析分為兩個階段，即事前分析和事后測試。 事前分析（priori analysis），求出該算法的一個時間界限函數，用于對計算時間的漸進表示，假定某一算法的計算時間是f(n)，其中變量n表示輸入或輸出量，它可以是兩者之和，也可以是它們之一的一種測度，例如數組的維數、圖的邊數等，f(n)與機器和語言有關。g(n)是在事前分析中確定的某個形式很簡單的函數，是獨立于機器和語言的函數，例如nm、logn、2n、n!等。給出定義： 若存在兩個正常數c和n0，對于所有的n≥n0，下式成立 ｜f(n)｜ ≤ c｜ g(n)｜記作 f(n)= o(g(n)) 因此，當講一個算法具有o(g(n))的計算時間時，指的是若該算法用n值不變的同一類數據在某臺機器上運行時，所用的時間是小于｜ g(n)|的一個常數倍，所以g(n)是計算時間f(n)的一個上界函數，f(n)的數量級就是g(n)，在確定f(n)的數量級時總是試圖求出最小的g(n)，使得f(n)= o(g(n))。 事后測試（posteriori testing），收集該算法的執行時間和實際占用空間的統計資料，是在對算法進行設計、確認、事前分析、編碼和調試后要做的工作，即作時空性能分布圖，事后測試的結果與所用機器相關。要確定算法的精確計算時間，必須了解時鐘的精確度以及計算機所用操作系統的工作方式。為避免因所用機器不同而出現誤差，有兩種可以選用的方法：一種方法是增加輸入規模，直到得到算法所需的可靠的時間總量；第二種方法是取足夠大的算法重復因子r，將該算法執行r次，然后用總的時間去除以r。 例如，對于事前分析為o(g(n))時間的算法，選擇按輸入不斷增大其規模的數據集，用這些數據集在計算機上運行算法程序，得出算法所使用的時間，畫出這一數量級的時間曲線，并與事前分析所得出的曲線比較。
<