[Algorithm] P/NP/NP-Complete/NP-Hard 定義

老是忘記這幾個名詞，還是做個筆記一下。

• 時間複雜度
•  在計算機科學中，演算法的時間複雜度是一個函數，用來描述了該演算法的運行時間等級[1]。
  
  例如  :
  void example(int n) {       // execute times
      int i , sum;                   //       1
      for ( i=0; i<n; i++ )       //       n        
      sum += i;                    //        1
  }                                     //   = n + 2 = O(n)
  => O(n) 表示對任何大小為n的輸入，最差只有n的時間即可運行完成
• 多項式複雜度 - O(1)、O(log(n))、O(n^a)
• 非多項式時間複雜度 - O(a^n)、O(n!)

• 問題的等級
• Unsolvable Problem (無解題)
• Intractable Problm (難解題 : O(a^n)以上的問題)
• NP-Problem
• P(Polynomial Time)-Problem

P: 確定多項式時間內可找到解的問題

NP(困難的問題):不確定多項式時間內可找到解的問題， 但有多項式時間被驗證解。(未找到已知的快速解法，但有快速可驗證的解法)

Ex : 81785036517是否否為質數? 不確定81785936517是否為質數，但可以驗證277877是否為81785936517的因子，並且確定可在多項式時間那處理完，故此問題為NP問題。

NP-Hard :不確定多項式時間內可找到解的問題，也不確定有多項式時間被驗證的解。

NP-Complete :　NP-Hard 與 NP問題的交集，即為NP-Complete的問題(參考圖一)。

圖一 : P=NP or P != NP
圖片來源 : 取至wiki

Reference :
[1] Wiki - 時間複雜度
[2] 論P,NP,NP-hard,NP-complete問題
[3] 漫谈算法（三）NP问题