[內容提要]
1、 演算法及其描述；
2、 演算法的特性；
3、 演算法的評價；
4、 時間和空間複雜性的計算和討論；
5、 演算法的優化方法；
[重點難點]
1、 演算法的描述及其結構化思想；
2、 演算法的評價：時間和空間複雜性；
3、 演算法的優化：如何解決時空的矛盾；
[內容講授]
一、演算法及其描述
演算法是對特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示乙個或多個操作。常見的演算法有：窮舉法，分治法，篩選法，構造法，貪心法，動態規劃等。
一般說來，演算法可以用自然語言、流程圖和程式來描述。下面通過乙個具體的例子來說明演算法的描述方法。
例1、h數問題（hnum）
[問題描述]
所謂ｈ數，是指該數除１以外最多只有2，3，5，7四種因子，如630即為ｈ數，而22不是。要求對鍵盤輸入的自然數ｎ，求出第ｎ個ｈ數。如ｎ=30，應輸出49。
規定要求的ｈ數不超出長整型數的範圍。
[演算法分析]
從ｈ數的定義可以看出，如果乙個數是ｈ數，那麼將它的2，3，5，7四種因子去掉以後必然是剩下1。下面就根據ｈ數的這一特性用窮舉法來解決這個問題。首先用自然語言描述該演算法。
演算法1_1：窮舉法計算第n個h數
第一步：從鍵盤輸入乙個自然數給n；
第二步：將h置為1，order置為1；
第三步：如果order=n ，則轉第七步；否則轉第四步；
第四步：h增加1，並將k的值置為h；
第五步：將k中的2，3，5，7四種因子去掉；
第六步：如果k=1，則order 增加1；
第七步：輸出h；
以上描述中第五步的描述不夠明確，下面對去掉k中因子i作更進一步的說明:
第1步：如果k是i的倍數，則轉第2步，否則演算法結束；
第2步：將k置為k/i；
第3步：轉第1步；
有了上述用自然語言描述的演算法後，就很容易編寫出求解ｈ數問題的程式（hnum1.pas），借助計算機來計算結果了。程式中將2，3，5，7存放在陣列mark中。
[參考程式1]
program hnum1(input，output);const mark:array [1..4] of integer=(2，3，5，7);var i，h，k，n，order:
longint;begin write('input n:'); readln(n);
h:=1; order:=1;
while order begin
h:=h+1; k:=h;
for i:=1 to 4 do
while k mod mark[i]=0 do k:=k div mark[i];
if k=1 then order:=order+1
end;
writeln('the no.'，n，' h number is '，h)
end.
[執行程式]下劃線表示輸入
input n:450
the no.450 h number is 23814
input n:1998
the no.1998 h number is 7056000
input n:4095
the no.4095 h number is 260112384
input n:5910
the no.5910 h number is 2143750000
[備註]
程式執行後雖然出了正確的解，但大家發現，隨著n越來越大，出解的時間就變得越來越慢，尤其是n>2000時，更是無法滿足競賽的時間要求（一般每個測試點的時限為1秒）。後面將討論這一問題的更高效的演算法。
二、演算法的特性
通過上面的例子，大家應該了解了演算法在程式設計中的作用，以及如何描述演算法了。既然演算法是求解問題的步驟或規則的描述，至於用什麼工具實現或由誰去執行，演算法描述中並沒有規定。現代演算法通常是作為程式設計的依據而言的。
乙個演算法雖然與用什麼語言去遍程、在什麼計算機上執行沒有必然的關聯，但作為演算法設計者來說，對於演算法的一些重要特性是應該掌握的。乙個演算法應該具有下列特性：
① 有窮性：乙個演算法必須總是(對任何合法的輸入值)在執行有窮步之後結束，且每一步都可在有窮時間內完成。
② 確定性：演算法的每一步，必須是確切地定義的，讀者理解時不會產生二義性。並且，在任何條件下，演算法只有唯一的一條執行路徑，即對於相同的輸入只能得出相同的輸出。
③ 輸入：乙個演算法有0個或多個輸入。它們是在演算法開始前對演算法給定的量，這些輸入取自於特定物件的集合。
④ 輸出：乙個演算法有乙個或多個輸出。它們是同輸入有某種特定關係的量。
⑤ 可行性：演算法應該是可行的。這意味著演算法中所有有待實現的運算都是相當基本的，也就是說，它們原則上都是能夠精確地進行的，甚至人們僅用筆和紙做有窮次運算即可完成。
三、演算法的評價
對於解決同乙個問題，往往能夠設計出許多不同的演算法。例如，對於資料的排序問題，我們可以用選擇排序、氣泡排序、插入排序、快速排序、希爾排序等多種演算法，對於這些排序演算法，他們各有優缺點，其演算法效能如何有待使用者的評價。因此，對問題求解的演算法優劣的評定稱為「演算法評價」。
演算法評價的目的，在於從解決同一問題的不同演算法中選擇出較為合適的一種演算法，或者是對原有的演算法進行改造、加工，使其更優、更好。
一般對演算法進行評價主要有四個方面：
1、演算法的正確性
正確性是設計和評價乙個演算法的首要條件，如果乙個演算法不正確，其它方面就無從談起。乙個正確的演算法是指在合理的輸入資料下，能在有限的執行時間內得到正確的結果。通過對資料輸入的所有可能情況的分析和上機除錯，以證明演算法是否正確。
2、演算法的簡單性
演算法簡單有利於閱讀，也使得證明演算法正確性比較容易，同時有利於程式的編寫、修改和除錯。但是演算法簡單往往並不是最有效。因此，對於問題的求解，我們往往更注意有效性。
有效性比簡單性更重要。
3、演算法的執行時間：時間複雜性
演算法的執行時間是指乙個演算法在計算機上運算所花費的時間。它大致等於計算機執行簡單操作（如賦值操作，比較操作等）所需要的時間與演算法中進行簡單操作次數的乘積。通常把演算法中包含簡單操作次數的多少叫做「演算法的時間複雜性」。
它是乙個演算法執行時間的相對量度，一般用數量級的形式給出。度量乙個程式的執行時間通常有以下兩種方法：
① 一種是「事後統計」的方法。因為很多計算機內部都有計時功能，有的甚至可精確到毫秒級，不同演算法的程式可通過一組或若干組相同的統計資料以分辨優劣。但這種方法有兩個缺陷：
一是必須先執行依據演算法編制的程式；二是所得時間的統計量依賴於計算機的硬體、軟體等環境因素，有時容易掩蓋演算法本身的優劣。因此人們常常採用另一種「事前分析估算」的方法。
② 「事前分析估算」的方法基於：乙個用高階程式語言編寫的程式在計算機上執行時所消耗的時間取決於下列因素：
1 依據的演算法選用何種策略。不同演算法、不同策略所消耗的cpu時間顯然是不同的；
② 問題的規模。例如求100以內還是1 000 000以內的素數；
③ 書寫程式的語言。對於同乙個演算法，實現語言的級別越高，執行效率就越低；
④ 編譯程式所產生的機器**的質量：編譯器的區別、版本會有所不同；
⑤ 機器執行指令的速度。
顯然，同乙個演算法用不同的語言實現，或者用不同的編譯程式進行編譯，或者在不同的計算機上執行時，效率均不相同。這表明使用絕對的時間單位衡量演算法的效率是不合適的。撇開這些與計算機硬體、軟體有關的因素，可以認為乙個特定演算法「執行工作量」的大小，只依賴於問題的規模（通常用整數量n表示），或者說，它是問題規模的函式。
乙個演算法是由控制結構（順序、分支和迴圈三種）和原操作（指固有資料型別的操作）構成的，則演算法時間取決於兩者的綜合效果。為了便於比較同一問題的不同演算法，通常的做法是，從演算法中選取一種對於所研究的問題（或演算法型別）來說是基本運算的原操作，以該基本操作重複執行的次數作為演算法的時間度量。
例如，在如下所示的兩個n*n的矩陣相乘的演算法中，「乘法」運算是「矩陣相乘問題」的基本操作。整個演算法的執行時間與該基本操作（乘法）重複執行的次數n3 成正比，記作
t（n）=o（n3）。
for i:=1 to n do
for j:=1 to n do
begin
c[i，j]:= 0;
for k:=1 to n do c[i，j]:= c[i，j]+a[i，k] * b[k，j]
end;
一般情況下，演算法中基本操作重複執行的次數是問題規模n的某個函式f（n），演算法的時間量度記作：
t（n）= o（f（n））
它表示問題規模n的增大、演算法執行時間的增長率和f（n）的增長率相同，稱作演算法的漸進時間複雜度，簡稱時間複雜度。
顯然，被稱作問題的基本操作的原操作應是其重複執行次數和演算法的執行時間成正比的原操作，多數情況下它是最深層迴圈內的語句中的原操作，它的執行次數和包含它的語句的頻度相同。語句的頻度指的是該語句重複執行的次數，例如：在下列三個程式段中，
1 x:=x+1
2 for i:=1 to n do x:=x+1;
3 for j:=1 to n do
for k:=1 to n do x:=x+1
含基本操作「x增1」的語句x:=x+1的頻度分別為1，n和 n2 ，則這三個程式段的時間複雜度分別為o（1），o（n），o（n2），分別稱為常量階、線性階和平方階。演算法還可能呈現的時間複雜度有：
對數階o（log n），指數階o（2n）等。在n很大時， 不同數量級時間複雜度顯然有o（1） 一般情況下，對乙個問題(或一類演算法)只需選擇一種基本操作來討論演算法的時間複雜度即可，有時也需要同時考慮幾種基本操作，甚至可以對不同的操作賦以不同權值，以反映執行不同操作所需的相對時間，這種做法便於綜合比較解決同一問題的兩種完全不同的演算法。
由於演算法的時間複雜度考慮的只是對於問題規模n的增長率，則在難以計算基本操作執行次數(或語句頻度)的情況下，只需求出它關於n的增長率或階即可，一般可忽略常數項、底階項、甚至係數。
例如，在下列程式段中:
for i:=2 to n do
for j:=2 to i-1 do x:=x+1
語句x:=x+1執行次數關於n的增長率為n2 ，它是語句頻度表示式(n-1)(n-2)/2中增長最快的一項。
4、演算法所占用的儲存空間：空間複雜性
演算法在執行過程中臨時占用的儲存空間的大小被定義為「演算法的空間複雜性」。空間複雜性包括程式中的變數、過程或函式中的區域性變數等所占用的儲存空間以及系統為了實現遞迴所使用的堆疊兩部分。演算法的空間複雜性一般也以數量級的形式給出。
考研及其評價
政治 1 任汝芬 1 4 任一不是必要的，任一和紅寶書買其中一本就可以了任二或陳先奎2000或高教1600應該任選一本 不要買多了，一本書做精了 任三和任四不應該少，很經典 2 肖秀榮的最後幾套卷子，可能時間不夠用，但是最起碼應該做選擇題，大題看一下。3 海天的28題。我的大題基本上就是靠這本書了，...
EVA模型及其評價
eva估價模型及其與fcff的比較 一 eva概述 經濟增加值的理論淵源是諾貝爾經濟學獎的獲得者默頓 公尺勒和弗蘭科 莫迪利亞尼關於公司價值的經濟模型。1991年，美國的一家諮詢公司斯特恩 斯圖爾特公司 stern stewart 提出了經濟增加值的評價方法。eva可以定義為 公司經過調整的淨營業利...
評價唐太宗及其
安德森的公共決策論 領導決策過程也就是公共政策的制定過程，而公共決策者的主要任務是制定以行政法規為核心的公共政策。安德森認為，領導決策的主要內容是關於制定法令 發布行政命令 頒布行政法規以及對法律做出解釋的決定。他把公共決策或政策制定與行政人員在執行政策過程中所做的決定區別開來，稱後者為 普通決策 ...