第1章 算法與程序設計簡介

算法分析與設計王宇160273615tlms327@163.com2013年2月25日課程安排：第1章算法與程序設計簡介第2章窮舉與回溯第3章遞歸與分治第4章遞推第5章貪心算法第6章動態(tài)規(guī)劃

第7章模擬第8章智能優(yōu)化第9章并行算法簡介實驗安排：窮舉與回溯算法實驗遞歸算法實驗分治算法實驗遞推算法實驗貪心算法實驗動態(tài)規(guī)劃實驗實驗要求：實驗報告：1、程序說明。說明程序的功能、結構。2、調試說明。包括上機調試的情況、上機調試步驟、調試所遇到的問題是如何解決的，并對調試過程中的問題進行分析，對執(zhí)行結果進行分析。3、寫出源程序和執(zhí)行結果。第1章算法與程序設計概述主要內容：1.1算法與算法描述

算法定義算法描述1.2算法復雜性分析時間復雜度空間復雜度1.3程序設計簡介算法與程序結構化程序設計1.1算法與算法描述1.1.1

算法算法是程序設計的基礎，是計算機科學的核心。算法是指解決某一問題的運算序列?；蛘哒f算法是問題求解過程的運算描述，一個算法由有限條可完全機械地執(zhí)行的、有確定結果的指令組成。3.

算法是滿足下列特性的指令序列：

(1)確定性組成算法的每條指令是清晰的，無歧義的。

(2)可行性算法中的運算是能夠實現的基本運算，每一種運算可在有限的時間內完成。

(3)有窮性算法中每一條指令的執(zhí)行次數有限，執(zhí)行每條指令的時間有限。(對任何的合法輸入，算法總能在運算有限步后終止)

(4)輸入一個算法有零個或多個輸入。

(5)輸出一個算法至少產生一個量作為輸出。

算法的生成步驟設計確認分析編碼檢查調試計時算法的學習內容如何設計算法如何表示算法如何確認算法算法確認：一旦設計出了算法，就應證明它對所有可能的合法輸入都能算出正確的答案，這一工作稱為~

程序證明：證明程序對所有可能的合法輸入都能得到正確的結果，這一工作稱為~如何分析算法如何測試程序調試調試：在抽象數據集上執(zhí)行程序，以確定是否會產生錯誤結果。作時空分布圖：4.

選擇算法的標準

通常求解一個問題可能會有多種算法可供選擇，選擇的主要標準是算法的正確性和可靠性。其次是算法所需要的存儲空間少和執(zhí)行時間短等。在實際工程中我們遇到許多高難度計算問題，有的問題在巨型計算機上用普通算法來求解可能要數個月的時間，而且很難找到精確解。但用一個好的算法，即使在普通的個人電腦上，可能只需數秒鐘就可以求得解答。1.1.2

算法描述1.

描述算法的方式

算法是問題的程序化解決方案。一個問題可以設計不同的算法來求解，同一個算法可以采用不同的形式來表述。描述算法可以有多種方式，如自然語言方式、流程圖方式、偽代碼方式、計算機語言表示方式與表格方式等。當一個算法使用計算機程序設計語言描述時，就是程序。

2.

算法描述舉例

【例1.1】求兩個整數a,b(a>b)的最大公約數的歐幾里德算法:(1)a除以b得余數r;若r=0,則b為所求的最大公約數。

(2)若r≠0,以b為a,r為b,繼續(xù)(1)。注意到任兩整數總存在最大公約數,上述輾轉相除過程中余數逐步變小,相除過程總會結束。歐幾里德算法又稱為“輾轉相除”法，具體描述如下：輸入正整數a,b;if(a<b){c=a;a=b;b=c;}/*交換a,b,確保a>b*/r=a%b;while(r!=0){a=b;b=r;/*實施"輾轉相除"*/r=a%b;}printf(最大公約數b);

算法復雜性是算法運行時所需的計算機資源的量的高低體現運行該算法所需計算機資源的多少。算法的復雜性越高，所需的計算機資源越多；反之，算法的復雜性越低，所需的計算機資源越少。計算機資源，最重要的是時間資源與空間資源。需要計算機時間資源的量稱為時間復雜度，需要計算機空間資源的量稱為空間復雜度。算法分析是指對算法的執(zhí)行時間與所需空間的估算，定量給出運行算法所需的時間數量級與空間數量級。

1.2算法復雜性分析

在分析算法時，隱藏細節(jié)的數學表示法成為大寫O記法一個算法的時間復雜度是指算法運行所需的時間。一個算法的運行時間取決于算法所需執(zhí)行的語句（運算）的多少。算法的時間復雜度通常用該算法執(zhí)行的總的語句（運算）的數量級決定。就算法分析而言，一條語句的數量級即執(zhí)行它的頻數，一個算法的數量級是指它所有語句執(zhí)行頻數之和。

1.2.1時間復雜度時間復雜度定義

算法的計算時間f（n）定義：對于一個數量級為的算法，如果存在兩個正常數c和m，對所有的n≥m，有

稱當n充分大時，f（n）有上界，且稱g（n）為它的一個上界，記作。該算法具有的運行時間，是指當n足夠大時，該算法的實際運行時間不會超過的某個常數倍時間。

2.

例如程序段：

for(k=1;k<=n;k++){x=x+y;y=x+y;s=x+y;}每個賦值語句執(zhí)行頻數為n，該算法的數量級為3n；其計算時間即時間復雜度為O(n)。

3.

例如程序段：for(t=1,k=1;k<=n;k++){t=t*2;

for(j=1;j<=t;j++)s=s+j;}內循環(huán)賦值語句執(zhí)行頻數因為所以算法的時間復雜度為O()。

證明：設f(n)=3(n+1)2,g(n)=n2。那么有f(n)=O(g(n))4.

算法時間關系：常見多項式時間算法:常見指數時間算法:一般地，當n取值比較大時，在計算機上實現指數時間算法是不可能的，就是比時間復雜度高的多項式時間算法運行也很困難。

35.

兩個定理定理1.1時間復雜度符號O有以下運算規(guī)則：

O(f)+O(g)=O(max(f,g))(1.1)

O(f)O(g)=O(fg)(1.2)定理1.2如果是n的m次多項式，則

(1.3)【例1.2】估算下列程序段代表算法的時間復雜度。for(k=1;k<=n;k++)

for(j=1;j<=k;j++){ x=k+j; s=s+x;}【例1.3】估算下列程序段代表算法的時間復雜度。(1)t=1;m=0;

for(k=1;k<=n;k++){t=t*2;

for(j=t;j<=n;j++)m++;}時間復雜度為O(nlogn).(2)m=0;

for(k=1;k<=n;k++)

for(j=k*k;j<=n;j++)m++;時間復雜度為O().注意(1)、(2)中m++語句的執(zhí)行次數的計算一個算法的運行時間，與問題的規(guī)模相關，也與輸入的數據相關。對算法的改進與優(yōu)化，主要表現在有效縮減算法的運行時間與所占空間。例如把求解某一問題的算法時間從優(yōu)化縮減為就是一個了不起的成果?；蛘甙亚蠼饽骋粏栴}的算法時間的系數縮小，例如從2n縮小為3n/2，盡管其時間數量級都是，系數縮小了也是一個算法改進的成果。

算法的空間復雜度是指算法運行的存儲空間，是實現算法所需的內存空間的大小。一個程序運行所需的存儲空間通常包括固定空間需求與可變空間需求兩部分。固定空間需求包括程序代碼、常量與結構變量等所占的空間?？勺兛臻g需求包括數組元素所占的空間與運行遞歸所需的系統(tǒng)?？臻g等。二維或三維數組是空間復雜度高的主要因素之一。在算法設計時，為降低空間復雜度，要注意盡可能少用高維數組。

1.2.2

空間復雜度

1.2.1

算法與程序

1.

基本概念算法是程序設計的基礎，是程序的核心。程序是某一算法用計算機程序設計語言的具體實現。具體來說，一個算法使用C語言描述，就是C程序。上機實踐是檢驗算法與程序的標準。

1.2程序設計簡介

2.程序的內容一個程序應包括對數據的描述與對運算操作的描述兩個方面的內容。著名計算機科學家沃思(NikiklausWirth)就此提出一個公式：數據結構＋算法＝程序

(1.4)數據結構是對數據的描述，而算法是對運算操作的描述。1.4程序實現求兩個整數a,b的最大公約數(a,b)的歐幾里德算法(見例1.1)，并應用歐幾里德算法求n個整數的最大公約數。解：在歐幾里德算法描述基礎上進行數據描述即為求整數的最大公約數的程序。(1)求兩個整數的最大公約數程序實現設置算法中的相關變量a,b,c,r為長整型變量，即有3.程序設計舉例/*求整數a,b的最大公約數（a,b）*/#include<stdio.h>voidmain(){longa,b,c,r;

printf("請輸入整數a,b:");

scanf("%ld,%ld",&a,&b);/*輸入整數a,b*/

printf("(%ld,%ld)",a,b);

if(a<b){c=a;a=b;b=c;}/*交換a,b,確保a>b*/r=a%b;

while(r!=0){a=b;b=r;/*實施"輾轉相除"*/r=a%b;}

printf("=%ld\n",b);/*輸出求解結果*/}(2)求n個整數的最大公約數程序實現對于3個以上整數,最大公約數有以下性質:(a1,a2,a3)=((a1,a2),a3)(a1,a2,a3,a4)=((a1,a2,a3),a4),...

應用這一性質,要求n個數的最大公約數,先求出前n-1個數的最大公約數b,再求第n個數與b的最大公約數；要求n-1個數的最大公約數,先求出前n-2個數的最大公約數b,再求第n-1個數與b的最大公約數；依此類推。因而，要求n個整數的最大公約數，需應用n-1次歐幾里德算法。

為輸入與輸出方便，把n個整數設置成m數組，m數組與算法中的相關變量a,b,c,r設置為長整型變量，個數n與循環(huán)變量k設置為整型。即有/*求n個整數的最大公約數*/#include<stdio.h>voidmain(){int

k,n;longa,b,c,r,m[100];

printf("請輸入整數個數n:");/*輸入原始數據*/

scanf("%d",&n);

printf("請依次輸入%d個整數:",n);

for(k=0;k<=n-1;k++) {printf("\n請輸入第%d個整數：",k+1);scanf("%ld",&m[k]);}b=m[0];

for(k=1;k<=n-1;k++)/*控制應用n-1次歐幾里德算法*/{a=m[k];

if(a<b){c=a;a=b;b=c;}/*交換a,b,確保a>b*/r=a%b;

while(r!=0){a=b;b=r;/*實施"輾轉相除"*/r=a%b;}}printf("(%ld",m[0]);/*輸出求解結果*/

for(k=1;k<=n-1;k++)

printf(",%ld",m[k]);

printf(")=%ld\n",b);}

1.3.2結構化程序設計

1.幾個概念不應該把面向對象與面向過程對立起來。在面向對象程序設計中仍然要用到面向過程的知識。面向過程程序設計通常由結構化程序設計實現。任何簡單或復雜的算法都可以由順序結構、選擇結構和循環(huán)結構這三種基本結構組合而成。順序結構、選擇結構和循環(huán)結構被稱為程序設計的三種基本結構，也是結構化程序設計必須采用的結構。

2.結構化程序設計的基本要點（1）自頂向下,逐步求精；（2）模塊化設計；（3）結構化編碼。自頂向下是指對設計求解的問題要有一個全面的理解，從問題的全局入手，把一個復雜問題分解成若干個相互獨立的子問題。逐步求精是指程序設計的過程是一個漸進的過程。

模塊化就是把大程序按照功能分為若干個較小的程序。一個程序是由一個主控模塊和若干子模塊組成的。主控模塊用來完成某些公用操作及功能選擇，而子模塊用來完成某項特