-
- 算法的特性
- 時間複雜度
- 空間複雜度
算法的特性
1. 有窮性：由若幹條指令組成的有窮序列，總是在執行若幹次後結束，不可能永不停止
2. 确定性：每條語句有确定的含義，無歧義
3. 可行性：在目前環境條件下可以通過有限運算實作
4. 輸入輸出：有零個或多個輸入，一個或多個輸出
“好”算法的标注如下
1. 正确性：滿足具體問題的需求，程式運作正常無文法錯誤，能通過軟體測試，達到預期的需求
2. 易讀性：辨別符命名規則，簡潔易懂，注釋語句恰當适量，友善自己和他人閱讀，便于後期調試和修改
3. 健壯性：對于非法資料及操作有較好的反應和處理
4. 高效性：指算法運作效率高，即算法運作所消耗的時間短。是以我們将算法基本運算的執行次數作為時間複雜度的衡量标準
5. 低存儲性：低存儲性是指算法所需要的存儲空間低。是以算法占用的控件大小稱為空間複雜度
時間複雜度
定義：算法運作需要的時間，一般将算法的執行次數作為時間複雜度的度量标準
//算法1_1
sum=; //運作1次
total=; //運作1次
for(i=;i<=n;i++){ //運作n次
sum+=i; //運作n次
for(j=;j<=m;j++){ //運作n*n次,嵌套循環
total+=i*j; //運作n*n次
}
}
T（n）=++n+n+n*n+n*n
備注：運作次數中有高次方時，一般以最高次方來計算算法的運作時間
備注：在算法分析中，漸近複雜度是對算法運作次數的粗略估計，大緻反映問題規模增長趨勢，而不必精确計算算法的運作時間，在計算漸近時間複雜度時，可以隻考慮對算法運作時間貢獻最大的語句，而忽略那些運算次數少的語句。循環語句中處在循環内層的語句往往運作次數最多
不是每個算法都能直接計算運作次數
如下算法1_2
findx(int x){
foor(int i=;i<n;i++){ //在a[n]數組中順序查找x
if(a[i]==x)
return i; //傳回其下标i
}
return -;
}
此類型算法我們就很難計算其到底執行了多少次，因為這依賴于i在資料中的位置，是以我們隻能計算其平均執行次數為（n+1）/2
有些算法，如排序，查找，插入等算法，可以分為最好，最壞和平均情況分别求算法漸近複雜度，但是我們考察一個算法通常考察最壞的情況，而不是最好的情況
空間複雜度
定義：算法占用的空間大小，一般将算法的輔助空間作為衡量空間複雜度的标準，主要包括三部分
1. 輸入/輸出資料
2. 算法本身
3. 額外需要的輔助空間
算法1_3
//将兩個數交換，并分析其空間複雜度
swap（int x,int y）{ //x與y交換
int temp;
temp=x; //此時temp為輔助空間
x=y;
y=temp;
}
該算法使用了一個輔助空間temp，空間複雜度為O（1）
注意：遞歸算法中，每一次遞推需要一個棧空間來儲存調用記錄，是以空間複雜度需要計算遞歸棧的輔助空間
算法1_4
fac(int n){
if(n<){ //小于零的數無階乘值
printf("n<0,data error!");
return -;
}else if(n== || n==){
return ;
}else{
return n*fac(n-);
}
}
遞推與回歸過程如下圖：
此時，計算機内部是使用一種稱為“棧”的資料結構，其特性為不允許中間插入或抽取，是以稱為“後進先出”
因為劃分棧空間的數量取決于n的值，是以此算法的空間複雜度為O(n)，時間複雜度也為O(n)
n爆炸增量問題
一棋盤麥子故事告訴我們，當高次方到達一定程度，會出現爆炸性增長，如2的64次方達到了将近7730億，假如算法的時間複雜度達到了O(2^n)會怎麼樣？
常見的算法時間複雜度有一下幾類
1. 常數階：常數階的算法運作的次數是一個常數
2. 多項式階：很多算法時間複雜度是多項式，通常用O(n)，O(n^2)表示
3. 指數階：指數階時間複雜度運作效率極差，O(2^n)使用這樣的算法要慎重
4. 對數階：對數階時間複雜度運作效率較高，常見的有O(logn)，O(nlogn)
從指數階增量随着x的增加而急劇增加，而對數階增加緩慢，他們之間的關系為：
O(1)
Fib1(int n){
if(n<){
return -;
} if(n== || n==){
return ;
return Fib1(n-)+Fib1(n-);
}
}
//算法複雜度
n=時，T(n)=;
n=時，T(n)=;
n=時，T(n)=; //調用Fib1(2),Fib(1)和執行一次加法運算Fib1(2)+Fib1(1)
算法改進，算法1_6
既然斐波那契數列中的每一項是前兩項之和，如果記錄前兩項的值，隻需要一次加法運算就可以得到目前項，我們可以用數組
Fib2(int n){
if(n<){
return -;
}
int *a=new int[n];
a[]=;
a[]=;
for(int i=;i<=n;i++){
a[i]=a[i-]+a[i-];
}
return a[n];
}
很明顯，時間複雜度為O(n)
此算法使用了一個輔助數組記錄中間結果，空間複雜度也為O(n)，其實我們隻需要得到第n個斐波那契數，直接結果隻是為了下一次使用，根本不用記錄下來，是以我們可以采用疊代法進行算法設計
算法1_7
Fib3(int n){
int i,s1,s2;
if(n<){
return -;
}if(n== || n==){
return ;
}
s1=;
s2=;
for(i=;i<=n;i++){
s2=s1+s2; //輾轉相加法
s1=s2-s1;//記錄前一項
}
return s2;
}
疊代過程如下：
此算法使用了若幹個輔助變量，疊代輾轉相加，每次記錄前一項，時間複雜度為O(n)，但空間複雜度降到O(1)
我們還能繼續降階麼？可以，最多可以降到對數階O(logn)