- Misc.
- 猜解
- 代入用數學歸納法求證。
- 列出每層遞迴的成本,並依樹的高度來估計時間複雜度。
比
- Case 1.
$n^{\log_b(a)}$ 大,則$T(n) = \Theta(n^{\log_b(a)})$ - Case 2. 平手,則
$T(n) = \Theta(n^{\log_b(a)}\log(n)) $ - Case 3.
$\log_n(f(n))$ 大,且$af(\frac{n}{b}) = c(f(n)), c<1, n\geq n_0$ ,則$T(n)=\Theta(f(n))$
- 使用比較大小的排序終究無法逃脫決策樹模型的掌控,也就是
$\Omega(nlogn)$ 的限制。
Algorithm_Examples/src/Sorting/MergeSort.ts
Lines 3 to 42 in 214cf53
Algorithm_Examples/src/Sorting/HeapSort.ts
Lines 3 to 54 in 214cf53
Algorithm_Examples/src/Sorting/QuickSort.ts
Lines 3 to 36 in 214cf53