演算法›Ch2 分治法第 2 題/共 12 題
2. 複雜度分析、分治法、Master Theorem
#AL-02-002中複雜度分析分治法Master Theorem
In 2022, DeepMind's AlphaTensor discovered a new state-of-the-art strategy for multiplying two matrices using only 47 multiplications (under a special arithmetic) instead of the original 49. By integrating this method into a standard divide-and-conquer framework, the complexity of multiplying two matrices is reduced to . Compute based on the above information to get the tightest upper bound.
參考答案與解析
答案 (C):分治後用 47 次乘法完成 4×4 矩陣乘法,複雜度遞迴式 T(n)=47·T(n/4)+O(n^2),由 Master Theorem,n^{log_4 47} 支配 O(n^2) 項(因為 log_4 47 ≈ 2.79 > 2),故 k=log_4 47。
📄 台大115
▤完整推導請見《WH 資工筆記 · 演算法》Ch2 分治法