資料結構-複雜度計算
前情提要
在準備研究所面試與專題報告時,演算法分析 往往是必考重點。本文彙整了從最基礎的漸進符號定義(O, Ω, Θ, o, ω)到空間複雜度、遞迴關係、以及Master 定理與其擴展版本的精華內容,並搭配典型範例與 C/C++ 實作要點,助你快速掌握:
- 各種 Asymptotic Notation 的嚴謹定義與相互關係
- 空間複雜度 分析要點與 C/C++ 參數傳遞差異
- 遞迴函式 的展開帶入法與 Master
定理(原始/擴展)
- 限定與推導法(Limit Method)、等價證明、Log Method 常見技巧
- 典型範例:Selection Sort、階乘、遞迴和遞迴樹、Stirling 公式等
無論你是研究所考生、面試準備者,或想系統複習演算法理論的工程師,這篇筆記都能提供一個清晰、一站式的參考架構。讓我們從基本概念出發,一步步深入最核心、最實用的分析技巧!