#karatsuba

Stanford CS161 Lecture 1：為什麼分析演算法要從 Karatsuba 乘法開始

把兩個 n 位數各切成兩半，直覺分治仍要做 4 個子乘法，時間沒有離開 n²；Karatsuba 用 (a+b)(c+d)-ac-bd 算交叉項，把分支降到 3，得到約 n^1.585 的成長率。