# [資料結構] 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 ㄅ歉我不知道中文是啥
* 雖然剛剛說了，我們會以步驟來分析一段演算法/程式的好壞，但實際上是怎麼做的？這裡有三種分析標準：
1. Big-Oh: $f(n)=O(g(n))$
* Iff exist positive constants **c** and $n_0$ that $f(n)\leq cg(n)$ for all n when $n>n_0$.
* 簡單來說就是取上界。有種取極限以忽略常數和非最大冪次項的感覺。
2. Omega: $f(n)=\Omega(g(n))$
* Iff exist positive constants **c** and $n_0$ that $f(n)\geq cg(n)$ for all n when $n>n_0$.
* 對啦就是取下界
3. Theta: $f(n)=\Theta(g(n))$
* Iff exist positive constants $c_1$, $c_2$ and $n_0$ that $c_1g(n)\geq f(n)\geq c_2g(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`