本課主題： 算法效率的度量和存儲空間需求

教學目的： 掌握算法的漸近時間復雜度和空間復雜度的意義與作用

教學重點： 漸近時間復雜度的意義與作用及計算方法

教學難點： 漸近時間復雜度的意義

授課內容：

一、算法效率的度量

算法執行的時間是算法優劣和問題規模的函數。評價一個算法的優劣，可以在相同的規模下，考察算法執行時間的長短來進行判斷。而一個程序的執行時間通常有兩種方法：

1、事后統計的方法。

缺點：不利于較大范圍內的算法比較。（異地，異時，異境）

2、事前分析估算的方法。

程序在計算機上運行所需時間的影響因素
算法本身選用的策略
問題的規模	規模越大，消耗時間越多
書寫程序的語言	語言越高級，消耗時間越多
編譯產生的機器代碼質量
機器執行指令的速度

綜上所述，為便于比較算法本身的優劣，應排除其它影響算法效率的因素。

從算法中選取一種對于所研究的問題來說是基本操作的原操作，以該基本操作重復執行的次數作為算法的時間量度。 （原操作在所有該問題的算法中都相同）

T(n)=O(f(n))

上示表示隨問題規模n的增大，算法執行時間的增長率和f(n)的增長率相同，稱作算法的漸近時間復雜度，簡稱時間復雜度。

求4*4矩陣元素和，T(4)=O(f(4)) f=n*n;	sum(int num[4][4]) { int i,j,r=0; for(i=0;i<4;i++) for(j=0;j<4;j++) r+=num[i][j]; /*原操作*/ return r; }
最好情況： T（4）=O（0） 最壞情況： T（4）=O（n*n）	ispass(int num[4][4]) { int i,j; for(i=0;i<4;i++) for(j=0;j<4;j++) if(num[i][j]!=i*4+j+1) return 0; return 1; }

原操作執行次數和包含它的語句的頻度相同。語句的頻度指的是該語句重復執行的次數。

語句	頻度	時間復雜度
{++x;s=0;}	1	O(1)
for(i=1;i<=n;++i) {++x;s+=x;}	n	O(n)
for(j=1;j<=n;++j) for(k=1;k<=n;++k) {++x;s+=x;}	n*n	O(n*n)
		O(log n)

 

基本操作的執行次數不確定時的時間復雜度
平均時間復雜度	依基本操作執行次數概率計算平均
最壞情況下時間復雜度	在最壞情況下基本操作執行次數

 

二、算法的存儲空間需求

類似于算法的時間復雜度，空間復雜度可以作為算法所需存儲空間的量度。

記作：

S(n)=O(f(n))

若額外空間相對于輸入數據量來說是常數，則稱此算法為原地工作。

如果所占空間量依賴于特定的輸入，則除特別指明外，均按最壞情況來分析。

三、總結

漸近時間復雜度

空間復雜度