[資料結構] CH2. Performance Analysis

時間複雜度與空間複雜度

一個程式/演算法的好壞，我們可以從時間與空間兩個面相去分析。
至於到底是時間還是空間重要，我們要由我們程式的目的去看。即時性、可讀性…等，不同的需求會讓我們對程式有不同的寫法。

空間複雜度

一般我們會將空間複雜度分為兩個部份來分析：
- Fixed part：
  - 對於一些程式常數、基本變數所需要的儲存空間。
- Variable part：
  - 運算所需的參考變數，或是遞迴的堆疊指標所需要的儲存空間。
我們有時候會將空間複雜度這樣表示：
$S (P) = c + S_{p}$ 。其中c指的就是Fixed part；
$S_{p}$ 指的是Variable part。
在討論空間複雜度時，我們只注重Variable part。

時間複雜度

時間複雜度一樣也可以分成兩個部分：
- Compile time：
  - 編譯code所需的時間。
- Run (execution) time
  - 實際執行時所需的時間。
也一樣可以這樣表示：
$T (P) = c + T_{p}$ ，c為Compile time；
$T_{p}$ 為Run time。
聰明如你，我們只注重Run time。
在這裡我們Run time又有兩種方式可以分析：
1. 根據這個程式從執行到結束花了多久的時間。
2. 根據我們執行了幾個步驟才完成目的。
  - 由於前者會受到CPU強度而受到影響，通常我們又使用後者分析。

Asymptotic Notations ㄅ歉我不知道中文是啥

雖然剛剛說了，我們會以步驟來分析一段演算法/程式的好壞，但實際上是怎麼做的？這裡有三種分析標準：

Big-Oh:
$f (n) = O (g (n))$
- Iff exist positive constants c and
  $n_{0}$ that
  $f (n) \leq c g (n)$ for all n when
  $n > n_{0}$ .
- 簡單來說就是取上界。有種取極限以忽略常數和非最大冪次項的感覺。
Omega:
$f (n) = Ω (g (n))$
- Iff exist positive constants c and
  $n_{0}$ that
  $f (n) \geq c g (n)$ for all n when
  $n > n_{0}$ .
- 對啦就是取下界
Theta:
$f (n) = Θ (g (n))$
- Iff exist positive constants
  $c_{1}$ ,
  $c_{2}$ and
  $n_{0}$ that
  $c_{1} g (n) \geq f (n) \geq c_{2} g (n)$ for all n when
  $n > n_{0}$ .
- 上下界一起取。

這些符號可以稱做漸進符號，用於觀察一個function複雜度的成長率。

因為不想打一堆LaTeX語法，很麻煩，所以這邊就不附上題目了，請自行練習。

資料型態(Data Type)

一個資料型態應該要考慮到它的Objects和Operations。
- 像是int這個資料型態，Objects是1.2.3.4…等等的數字，而Operations是+ - * / 等等的運算行動。

抽象資料型態(Abstract Data Type)

抽象資料型態ADT，會根據你後來才提供的資料型態，提供更多的Operations。
講起來有點…抽象，因為它是"抽象"資料型態。
- 好，當我沒說。
經典的例子就是stack、queue等等的資料型態。
C++中提供的STL中，就有大量的ADT，像是map vector list 之類的，如果你有用過就懂了。

tags: `DS` `note`