地特三等申論題
111年
[資訊處理] 資料結構
第 一 題
📖 題組：
請用 Big-O 符號來表示下列函式的成長速率，並說明之：
請用 Big-O 符號來表示下列函式的成長速率，並說明之：
📝 此題為申論題，共 2 小題
小題 (一)
T(n) = 3n^3 + 7n^3√n + n^3 log n（5 分）
思路引導 VIP
遇到多項式加總的 Big-O 求值題，首要步驟是將所有項轉換為易於比較的指數形式（如將根號轉換為次方）。接著根據漸進複雜度的規則，比較多項式、根號與對數的成長級別（如 n^c > log n），找出成長速率最快的主導項，並捨去常數係數與低次項即可得解。
小題 (二)
T(n) = 2T(n/2) + n^2（10 分）
思路引導 VIP
看到此類分治法（Divide and Conquer）的遞迴關係式，應首選「大師定理（Master Theorem）」來快速判斷時間複雜度的落點；若需更嚴謹展示計算邏輯，可利用「遞迴展開法（遞迴樹法）」列出等比級數來推導總和。