2018q1 Homework3 (list)
===========================

contributed by < `BroLeaf`>

###### tags `BroLeaf`

## 生日悖論

- [ ] 自我檢查事項
### 如何透過近似的運算式，估算上述機率計算呢？附上有效的 LaTeX 算式
有 n 個人生日不重複的機率
$P'(X) = \frac{365}{365}\times\frac{364}{365}\times\frac{363}{365}\times\frac{362}{365}\times\cdots\times\frac{366-n}{365}$
$= 1\times(1-\frac{1}{365})\times(1-\frac{2}{365})\times(1-\frac{3}{365})\times\cdots\times(1-\frac{n-1}{365})$
引入Talor series
$e^{x}=1+x+{\frac {x^{2}}{2!}}+\cdots$
$當\ X<<1時，{\displaystyle e^{x}\approx 1+x}$
原式變為$1\times e^{-\frac{1}{365}}\times e^{-\frac{2}{365}}\times e^{-\frac{3}{365}}\times \cdots \times e^{-\frac{n-1}{365}}$
$=e^{-\frac{n(n-1/2)}{365}}=e^{-\frac{n(n-1)}{730}}$
則有 n 個人生日會重複的機率為$1-P'(n) = 1-e^{-\frac{n(n-1)}{730}}$

## Linux 風格的 linked list

- [ ] 自我檢查事項:

* 為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？
* 參考[What is the difference between a macro and a function in C?](https://stackoverflow.com/questions/4990362/what-is-the-difference-between-a-macro-and-a-function-in-c)
* Advantages

* Time efficiency.
* Not need to pass arguments like function.
* It's preprocessed.
* Easier to Read.
* Disadvantages

* Very hard to debug in large code.
* Take more memory in stack compare to function. Suppose in the program that there a Macro which used 50 times that means it will consume memory 50 times but in function if a function is called 50 times it will take single memory every time because every time it deallocate that memory
* C 語言對於 macro 的處理是在 preprocessed 這個解段，基本上可以當做是在 compile time 完成的，所以比起在 run time 才處理 function 的 push、pop 自然會更有時間上的效率，而這些勢必要多犧牲一些在 memory 的空間來達到這樣的效果