重念一次早該補起來的「資料結構與演算法」。這篇筆記 Master Theorem 主定理簡介。
課程相關資訊
[連結]：https://hiskio.com/courses/572/lectures/29829
本篇範圍：Chapter 7
請注意：本系列文章為個人對應課程的消化吸收後，所整理出來的內容。換言之，並不一定會包含全部的課程內容，也有可能會添加其他資源來說明。
內容
由於當時在撰寫這個定律時，覺得所有的演算法都可以符合，因此被稱為 Master Theorem。若你可以得知一個程式執行的遞迴函式，那你就可求出時間複雜度 BigO。
Master Theorem
T(n) = a * T (n/b) + n^c
一個規模為 n 的問題，分成 a 個規模為 n/b 的子問題，並且需要花 O(n^c) 的時間將該層所有子問題合併起來。
以樹的角度來說就是 logbn 為樹高，a 是展開的子節點數量，n^logba 為所有葉子節點的數量。
因此合併時的時間複雜度，與 n^logba 所有葉子節點的數量兩者誰大，誰就決定時間複雜度
可以參考這篇文章的證明：
1. 時間複雜度 — 遞迴(下) — Master Theorem
2. 主定理 Master Theorem
