資料結構複習(一): 複雜度

我被課輔部拉來教資料結構了QQ，不過其實我最近也想複習資料結構啦!!

本文參考自浙江大學 劉越姥姥，線上課程連結詳見文末。

友站連結: https://noob.tw/data-structure/

學資料結構幹嘛?

1. JAVA2會用到，子賢會把你當掉
2. 資料結構幾乎是研究所必考考科，現在好好學對未來沒壞處
3. 資料結構也是各大公司招考時的考科

資料結構是什麼?

對我來說，資料結構是教你如何讓程式跑的更迅速、更省空間、更規範。 想一個問題你要建一個圖書館，請問書怎麼放?

問題牽涉兩個層面

1. 我要如何插入書
2. 我要如何找到書
3. 書架要多大

資料結構離不開這三個問題: 插入、查找、空間

有三個方法

1. 隨便放，有書就塞，管他是小紅帽還是電腦網路概論。
2. 按ㄅㄆㄇ放。
3. 先分類，小紅帽放童話、電網放計算機，再按ㄅㄆㄇ放。

考慮一下優劣，考慮一下插入時間、空間，查找時間、空間。

答案:

• 所需空間: 3>2>1
• 插入時間: 1>2>3
• 查找時間: 3>2>>>>>>1

問題是我們要如何具體衡量?

時間複雜度

時間複雜度是程序所需要的處理時間，記做O()表示，n為變數假設執行10次則n=10，10000000次則n=1000000。以下為O(1)程式執行一次。

function a(int n){
  print("%d/n",n); //打印一次
}

以下O(N)

function a(int n){
  for(int i=0;i<n;i++){
    print("%d/n",i)   //由於for執行了N次
  }
}

猜猜以下執行幾次

double fun(int n,double a[],double x){
  double p;
  for(int i=0;i<n;i++)
    p+=(a[i]*pow(x,i)); //pow為指數，代表x被成i次
  return p;
}

解答: for的N * pow的 (N+N-1+N-2+…..1)=(N2+N)，但一般來說當N資料量巨大時可以捨棄尾數，因此我們可以說這個函數時間複雜度為O(N2)。

空間複雜度

空間複雜度其實就是空間大小啦!!一般來說出現在考陣列與遞規函數出現時。

void PrintN(int N){
  if(N>0){
    PrintN(N-1);
  }
  print("%d",N);
}

當遞規函數N呼叫下一個遞規時N-1，他會先保存現在狀態N進記憶體。當N=10000時，記憶體需要空間10000單位，所以空間複雜度為 O(N)。

!! 當我們在講O(x)時我們都是在講最壞的情況

試試看:

下面代碼的時間複雜度

if(A>B){
  for(i=0;i<N;i++){
    for(j=N*N;j>i;j--){
      A+=B;
    }
  }
}else{
  for(i=0;i<N*2;i++){
    for(j=N*2;j>i;j--){
      A+=B;
    }
  }
}

• 線上課程 : https://www.icourse163.org/course/ZJU-93001
• 推薦書籍 : https://detail.tmall.com/item.htm?spm=a230r.1.14.34.76ab237bQIMgVP&id=536108301585&ns=1&abbucket=9 (很好讀，強推)
• 參考 : https://noob.tw/data-structure/

資料結構複習(二):陣列&指針