# 台大 101 軟體
###### tags: `NTU` `101` `軟體`
1. (1) $n!$
(2) $2^k$
(3)
$$
2^k\ge n!\\
k\ge lg(n!)\ge nlgn
$$
2. (1) T
(2) F
:::info
$$
f(n)=g(n)=n\\
f(n)g(n)=n^2\notin O(nlgn)
$$
:::
(3) T
(4) T
(5) F
:::info
$$
f(n)=2n, g(n)=n\\
2^{2n}=4^n\notin 2^n
$$
:::
3. (1) $n\ge 86400$ (2) $n\ge 26$
4. (1) (b), 全為 black nodes
(2) a.
:::info
我是用刪去法選出 a 的，但我無法充分地說明 a 為何錯

Chaining 的 time complexity 為 $O(1+\alpha)$，open addressing 為 $O(\frac{1}{1-\alpha})$

$\alpha$ 很小的時候兩個應該差不多，但 $\alpha$ 很大時($\ge 0.7,0.8$ 之類的)就有差了
:::
(3) \(c\), bottom-up 才對
5. 什麼鬼
6. 好無聊的題目，懶得寫