[資料結構(Data Structure, DS)] 演算法評估與資料型別

1. 演算法評估
2. 時間複雜度(Time Complexity)
3. 空間複雜度(Space Complexity)

演算法評估

• 用空間和時間評估演算法效能
  • 時間複雜度(Time Complexity)
  • 空間複雜度(Space Complexity)
• 效能評估
  • 效能分析(Performance Analysis)：事前評估
  • 效能評估(Performance Measurement)：效能量測
• 評估時均假設處理的資料量為n到無窮大

時間複雜度(Time Complexity)

• 演算法執行時，所需花費的時間
• 分析方法：統計演算法中指令執行的次數
• 時間函式T(n) ：表示當輸入資料量為n時，演算法中指令所需執行的次數
• 計數規則
  • 註解、括號、函式宣告及變數宣告不列入執行時間計算
  • 變數宣告時若有指派初始值，則視為1次
  • 函式呼叫視為1次
  • 不考慮指令本身的複雜度或實際執行時間，一個指令皆視為1次

  • //假設某電腦執行加法要5微秒，減法要10微秒，乘法要20微秒
    不管實際執行時間A=0、A++、A--、A=A*5都視為執行一次
    

  • int sum(int[] data)                     // 0次
    {                                       // 0次
        int i;                              // 0
        int sum = 0;                        // 1
    
        //for迴圈最後會判斷條件不成立，跳離迴圈，所以比其內容多執行一次
        for(i = 0; i < data.length; i++){   // data.length+1次
            sum += data[i];                 // data.length次
        }                                   // 0次
        return sum;                         // 1次
    }
    

空間複雜度(Space Complexity)

• 演算法執行時，所需花費的記憶體
• 分析方法
  • 統計演算法中所使用的固定空間(Fixed Space)和變動空間(Variable Space)
  • 固定空間(Fixed Space, C)：非主要考量
    • 程式碼大小(Instruction Space)
    • 簡單變數(EX：int, float,...)
    • 常數
    • 固定大小的結構變數(EX：陣列、記錄、...等）
  • 變動空間(Variable Space, S_P )
    • 以傳值呼叫(Call By Value)傳遞的參數(EX：陣列)
    • 遞迴所需的堆疊空間
  • 固定空間通常都是必要的，所以當有使用空間限制的需求時，只會考慮能否節省變動空間
• 空間函式S(P) ：表示當輸入資料量為n時，演算法中指令所需執行的次數
  • S(P) = C + S_P

• int sampleFunction( int a, int b, int c)
  {
      return a * b + c * a / b;
  }
  

  S_P = 0

• int sum(int[] data)
  {
      int sum = 0;
      for(int i = 0; i < data.length; i++)
          sum += data[i];
      return sum;
  }
  

  假設int佔4bytes：

  • 若data為Call By Value S_P = 4bytes × data.length
  • 若data為Call By Address S_P = 0

• int rSum(int[] data, int n){
      if(n != 0)
          return rSum(data, n-1) + data[n-1];
      return data[0];
  }
  

  假設int佔4bytes, Address佔2bytes，data以Call By Address傳遞

  • SP(I)
    • 有結構變數，但不是Call by Value ⇒ 沒有變動空間
    • 遞迴所需的Stack空間 = (data的起始位址 + n的大小) + 返回位址 = ( 2 + 4 ) + 2 = 8Bytes
    • 遞迴n次
    • S_P = 8n Bytes