什么是演算法

演算法字面意思,計算方法;

演算法規定了求解給定型別問題所需的所有處理步驟以及執行順序,使得問題能在有限時間內機械的求解,一個演算法就是對特定問題求解步驟的一種描述,再具體一點,演算法是一段有窮的指令序列;演算法必須能使用某種語言描述;

例如:

計算1到5的和 ,這個需求,如何來實作,第一步做什么,第二步做什么,整個計算步驟和執行順序統稱為演算法,如果最終能夠在有限的步驟下求出正確的和,那這就是一個合格的演算法;

演算法的特點:

• 有窮性

  演算法必須在執行有窮步后結束

• 確定性

  演算法的每一個步驟都必須是明確定義的,

• 可行性

  演算法中的每一步都是可以通過已實作的操作來完成的

• 輸入

  一個演算法具備0或多個輸入

• 輸出

  一個演算法有一個或多個輸出,它們與輸入有著特定的關系

演算法與程式的區別,演算法只是一種描述,可以使用任何語言,但是通常不能直接被計算機運行,而程式則是演算法的具體實作,使用某種計算機語言;

演算法設計應滿足的要求

• 正確性:對于合法的輸入產生符合要求的輸出

• 易讀性:演算法應該盡可能易讀,便于交流,這也是保證正確性的前提(注釋可提高易讀性)

• 健壯性:當輸入非法資料時,演算法可作出適當反應而不至于崩潰(例如輸出錯誤原因);

• 時空性:指的是演算法的時間復雜度和空間復雜度,演算法分析主要也是分析演算法的時間復雜度和空間復雜的,其目的是提高演算法的效率;

演算法分析

解決同一問題的演算法可能有多種,我們希望從中選出最優的演算法,效率高的,占用空間小的,為此我們就需要對演算法進行評估和分析;

通常評估演算法根據兩個度量

• 時間復雜度:演算法運行完成所需的總步數(標準操作),通常是問題規模的函式
• 空間復雜度:演算法執行時所占用的存盤空間,通常是問題規模的函式

時間復雜度

確定演算法的計算量

• 合理選擇一種或幾種操作作為'標準操作',無特殊說明默認以賦值操作作為標準操作;

• 確定演算法共執行多少次標準操作,并將此次數規定為演算法的計算量

• 以演算法在所有時輸入下的計算量最大值作為演算法的最壞情況時間復雜度

• 以演算法在所有時輸入下的計算量最小值作為演算法的最好情況時間復雜度

• 以演算法在所有時輸入下的計算量平均值作為演算法的平均情況時間復雜度

• 最壞和平均情況時間復雜度統稱為時間復雜度;

  • 它們通常擁有相同的大O表示法

  • 如:最壞:O(n) 平均O(n/2) 忽略系數后都為O(N)

注意:時間復雜度通常以量級來衡量,也就是說不需要精確的計算到底執行了幾步,而是得出其計算量的數量級即可,并忽略常數,因為當數量級足夠大時,常數對于計算量的影響可以忽略不計;

如: (n-1)(n-2) 數量級為 n^2

時間復雜度使用大O表示,如O(1)

案例:

1.

void aFunction(){
    int c = 10 + 20;
  	int d = c * c;
		printf(d);
}

上列演算法若以賦值運算作為標準操作,則該演算法的計算量為2,其時間復雜度記為O(1),為什么是O(1)呢,是因為2是一個常數,常數對于函式的增長影響并不大,所以計算量為常數時表示為O(1),按照這種方式,即使計算量為2000,同樣記為O(1),稱為常數階

2.

void bFunction(int n){
  for(int i = 0;i < n;i++){ // n
    int c = 2 * i;// 1
    int d = 3 * i;// 2
  }
}

此時函式的回圈次數由未知數n來決定,回圈體內計算量為2,當n是一個自然數時,函式的計算量等于(n)(2),此時時間復雜度為O(n),無論用常數2對n進行加減乘除對于n的指數都沒有影響,當n足夠大時,內部的2次計算量可以忽略,所以記為O(n),稱為線性階

更粗陋的度量方法是函式體包含一層回圈時記為O(n)

3.

void bFunction(int n){
  for(int i = 0;i < n;i++){
      for(int j = 0;j < i;j++){
      }
  }
}

外層回圈次數為n,內層回圈次數隨著n的增長而增長且最大值為n-1次,那么整個函式的計算量為(n)(n-1),常數可以忽略,所以時間復雜度記為O(n^2) ,稱為平方階

粗陋的方法是有兩層嵌套回圈,且回圈次數都隨著n的增長而增長,所以是O(n^2),以此類推,但是要注意下面這種情況

4.

void bFunction(int n){
  for(int i = 0;i < n;i++){
      for(int j = 0;j < 3;j++){
      }
  }
}

此時內層回圈的回圈次數是固定(常數)所以不會影響計算量的數量級,時間復雜度記為O(n)

5.

void bFunction(int n){
  for(int i = 3;i < n;){
	  i *= 3;
  }
}

此時函回圈次數會隨著3回圈體中的常數3的的變化而變化,我們可以用對數來表示,

假設回圈次數為s,回圈條件可表示為 s = 3^s < n;(即i本身為3,其次冪會不斷的增長,但結果要小于n)

當然這里有個條件是i的初值必須和每次乘等的值相同,形成次冪的增長;

用對數表示為s = log3n,時間復雜度記為O(log3n),常數可以忽略,所以最后是O(logn)稱之為對數階

對數階的數量級小于線性階,因為若n的值相同,對數階計算量必然小于線性階

6.

void bFunction(int n){
 for(int i = 0;i < n;i++){
	 for(int j = 0;j < n;j++){
     	 for(int k = 0;k < n;k++){
       }
	 }   
 }
}

上述演算法時間復雜度為O(n^{3),3為常數,對應著回圈的嵌套層數即次冪為常數;也可以用O(n}C)表示,稱為多項式階

7.

void bFunction(int n){
  int num = n;
  for(int i = 0;i < n;i++){ //O(n)
		num *= n;
  }
  for (int j = 0;j<num;j++){ //O(n)
  }
}

上述函式輸入的引數n將作為num的次冪,假設回圈次數為s, s = 2^{n,那么時間復雜度為O(2}n),

稱之為指數階,可記為O(C^n)

8.

void bFunction(int n)
{
    for(int i=0;i<n;i++){
          for(int j=0;j<n;j++){
          }
    }	
  
 	  for(int i=0;i<n;i++){
	  }			    
}

對于順序運行的演算法,總時間復雜度等于演算法中最大時間復雜度,即O(n^2)

9.

void bFunction(int n)
{
  if(n % 2 ==0){
    for(int i=0;i<n;i++){
          for(int j=0;j<n;j++){
          }
    }	
  }else{
	  for(int i=0;i<n;i++){
	  }			    
  } 
}

對于具備分支結構的演算法,總時間復雜度等于演算法中時間復雜度最大路徑的復雜度,即O(n^2)

時間復雜度大小順序

常數 < 對數階 < 線性階 < 平方階 < 多項式階 < 指數階

O(1) < O(logn) < O(n) < O(n^2) < O(n^C) < O(C^n)

一般情況下,一個演算法的時間復雜度是演算法輸入規模的函式;

通常認為,具有指數階數量級的演算法是實際不可計算的,而量級低于平方階的演算法是高效的;

空間復雜度

確定演算法的空間占用量

空間復雜度是對一個演算法在執行程序中臨時占用存盤空間大小的度量;

一個演算法在執行期間所需要的存盤空間包括以下部分:

• 程式代碼本身所占用的空間
• 輸出資料所占用的空間
• 輔助變數所占用的空間

** 估算演算法空間復雜度時,一般值分析輔助變數所占用的空間;

程式代碼占用空間是固定的,通常比較小
輸入資料占用空間同樣較小

強調:無論是時間復雜度還是空間復雜度都用大O表示,表示方法也是相同的,不需要具體到幾次,只需要求出最大的數量級即可,同樣忽略系數,即復雜度對于常數的加減乘除是忽略不計的;

案例:

下列是兩個演算法,用于對陣列元素順序進行逆轉操作;

void f1(int a[],int n){
	int i,temp;
  for(i = 0;i < n/2-1;i++){
    temp = a[i];
    a[i] = a[n-1-i];
    a[n-1-i] = temp;
  }
}

上述演算法時間復雜度為O(n);空間復雜度為O(1);

決議:該演算法員工定義了兩個整型的輔助變數,i和temp,輔助變數的個數與輸入資料沒有關系,是固定的常量C,對于擁有常數階復雜度的演算法,其復雜度用O(1)表示;

void f2(int a[],int n){
	int i,b[n];
  for(i = 0;i < n;i++){
    b[i] = a[n-i-1];
  }
  for(i = 0;i < n;i++){
    a[i] = b[i];
  }
}

上述演算法時間復雜度為O(n);空間復雜度為O(1);

決議:

對于空間復雜度,其需要的計算量是(n)(2),大O表示為O(n);

對于空間復雜度,同樣是兩個變數,但是陣列b的空間大小是隨著輸入資料增長的,所以整體占用為 1 + n,大O表示為O(n);

可以發現空間復雜度相比時間復雜度更好度量,因為只需要根據定義的變數數量來計算即可,而時間復雜度會隨回圈陳述句而變化;

標籤：其他

上一篇：簡單實用演算法—獲取分頁總頁碼

下一篇：在線教育會是下一個風口嗎？