前幾個禮拜的內容中，我們快速的把JAVA的語法練習過了一遍，也實作了兩個小專案，但當我們學會了如何撰寫程式之後，下一步，我們就要開始注意程式碼的質量。

今天要提到的內容是複雜度。
在進入複雜度前，我們必須要先知道"演算法"這個詞，定義上來看："由有限步驟所構成的集合，演算法的定義為，一個可以用於解決某一個特定的問題的方法或算法。"

我們可以藉由將資料輸入進演算法，透過演算法產生輸出。

一般而言，演算法具有下列五個特性

1. 準確描述的輸入(Input): 演算法通常會接受一些輸入，加以處理或運算，而產生一些輸出值。這些輸入必須有清楚的型別和個數描述。

2. 明確性(Definiteness)及有效性(Effectiveness): 演算法需要透過一定的陳述，來清楚的表達其含意，並且能讓人們用紙筆來執行。

3. 正確性(Correctness or Definiteness): 演算法既是以解題為目的，所以我們必須能夠證明一演算法可以正確地解決問題。

4. 有限性(Finiteness): 演算法必須在有限步驟內結束。

5. 結果的描述和輸出(Output): 演算法在接受輸入並在運算過後，必會產生特定輸出。

總而言之，演算法的速度不是以秒計算，而是以步驟次數。

常見的六種時間複雜度與演算法

• O(1)：陣列讀取
• O(n)：線性搜尋
• O(log n)：二分搜尋
• O(nlogn)：合併排序
• O(n²)：選擇排序
• O(2^n)：費波那契數列

讓我們以其中幾個例子來看
1.陣列讀取O(1)

int[] a = {1,5,6,2,3,8};
a[0] = 1;
a[1] = 5;

在複雜度中，我們可以稱O(1)為"常數時間"，意思是不管上面範例中的陣列成長到多大，在已知陣列索引的情況下，對陣列元素做取值，其複雜度都會在同樣的一定時間，意即a[0]和a[1]所花時間是一樣的，

2.線性搜尋O(n)

int[] a = {1,5,6,2,3,8};
int target = 8;
for(int i=0; i<a.length; i++){
  if(a[i]==target){
     System.out.println("找到了!");
  }
}

讓我們看看這個例子，當我們想要在a陣列中搜尋8這個數字時，由於並不知道8位於哪個陣列索引，所以我們必須透過迴圈來搜尋，因為一維陣列是線性的，若在陣列中進行搜尋，即是所謂的線性搜尋。
而我們搜尋的時間將會depends on陣列a的長度，也就是說當a陣列長度為n時，我們最壞的情況要搜尋到n才找的到我們想要的元素。這就是為甚麼是O(n)的原因。

以上就是簡單的複雜度範例，明天見囉。

Hi, I am Grant.

個人部落格 - https://grantliblog.wordpress.com/
個人網站 - https://grantli-website.netlify.app/#/mainpage
我的寫作專題 - https://vocus.cc/user/5af2e9b5fd89780001822db4#