演算法›Ch2 分治法
第 2 題/共 12 題
◀ AL 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 4×44 \times 4 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 n×nn \times n matrices is reduced to O(nk)O(n^k). Compute kk based on the above information to get the tightest upper bound.

📄 台大115
跳轉到第題
▤完整推導請見《WH 資工筆記 · 演算法》Ch2 分治法
本章題號 · 1–12 / 12