第二節：算法
時間復雜度和空間復雜度
算法(Algorithm)：是對特定問題求解方法(步驟)的一種描述，是指令的有限序列，其中每一條指令表示一個或多個操作。
算法可以有三種表示形式：
- ?偽代碼
- ?自然語言
- ?流程圖
算法的五個特性
① 有窮性： 一個算法必須總是在執行有窮步之后結束，且每一步都在有窮時間內完成。
② 確定性：算法中每一條指令必須有確切的含義。不存在二義性。且算法只有一個入口和一個出口。
③ 可行性： 一個算法是能行的。即算法描述的操作都可以通過已經實現的基本運算執行有限次來實現。
④ 輸入： 一個算法有零個或多個輸入，這些輸入取自于某個特定的對象集合。
⑤ 輸出： 一個算法有一個或多個輸出，這些輸出是同輸入有著某些特定關系的量。
算法和程序是兩個不同的概念。
一個計算機程序是對一個算法使用某種程序設計語言的具體實 現。算法必須可終止意味著不是所有的計算機程序都是算法。
好算法標準
① 正確性： 算法應滿足具體問題的需求。
② 可讀性： 算法應容易供人閱讀和交流。可讀性好的算法有助于對算法的
理解和修改。
③ 健壯性： 算法應具有容錯處理。當輸入非法或錯誤數據時，算法應能
適當地作出反應或進行處理，而不會產生莫名其妙的輸出結果。
④ 通用性： 算法應具有一般性 ，即算法的處理結果對于一般的數據集合
都成立。
⑤ 效率與存儲量需求： 效率指的是算法執行的時間；存儲量需求指算法
執行過程中所需要的最大存儲空間。一般地，這兩者與問題的規模有關。
?效率 指的是算法執行的時間存儲量需求指算法執行過程中所需要的最大存儲空間
算法效率的度量
算法執行時間需通過依據該算法編制的程序在計算機上運行所消耗的時間來度量。
其方法通常有兩種：
事后統計：計算機內部進行執行時間和實際占用空間的統計。
問題：必須先運行依據算法編制的程序；依賴軟硬件環境，容易掩蓋 算法本身的優劣；沒有實際價值。
算法效率的度量
撇開軟硬件等有關部門因素，可以認為一個特定算法“運行工作量”的大小，只依賴于問題的規模（通常用n表示），表示成是問題規模的函數。
算法效率的度量
表示時間復雜度的階有：
O(1) ：常量時間階 O (n)：線性時間階
O(㏒n) ：對數時間階 O(n㏒n) ：線性對數時間階
O (nk)： k≥2 ，k次方時間階
其關系為：
O(1)<O(㏒n)<O(n)<O(n㏒n)<O(n2)<O(n3)
指數時間的關系為：
O(2 n )<O(n!)<O(n n )
?常量階
{++x; s=0 ;}
將x自增看成是基本操作，則語句頻度為１，時間復雜度為Ｏ(1) 。
將s=0也看成是基本操作，則語句頻度為２，時間復雜度仍為Ｏ(1)。
? 線性階
for(i=1; i<=n; ++i) {
++x;
s+=x ;
}
語句頻度為：2n，其時間復雜度為：O(n) ，即為線性階。
? 平方階
for(i=1; i<=n; ++i){
for(j=1; j<=n; ++j) {
++x;
s+=x ;
}
}
語句頻度為：2n2 ，其時間復雜度為：O(n2) ，即為平方階。
? 三次方階 
兩個n階方陣的乘法
for(i=1，i<=n; ++i)
for(j=1; j<=n; ++j) {
c[i][j]=0 ;
for(k=1; k<=n; ++k)
c[i][j]+=a[i][k]*b[k][j] ;
}
由于是一個三重循環，每個循環從1到n，則總次數為： n×n×n=n3 時
間復雜度為T(n)=O(n3)
小結：
空間復雜度的度量
空間復雜度(Space complexity) ：是指算法編寫成程序后， 在計算機中運行時所需存儲空間大小的度量。記作： S(n)=O(f(n)) 其中： n為問題的規模(或大小)
空間復雜度的度量
for(i=1; i<=n; ++i)
for(j=1; j<=n; ++j)
{ ++x; s+=x ; }
臨時變量為：i , j ，s，x；空間復雜度為：O(1) ，即常量階。
復習考研數據結構第二天！！！
