知识卡片
少一次乘法可改变指数
Strassen 用 7 次而非 8 次半规模矩阵乘法,换取常数次矩阵加减。
加减只需 Θ(n²),形成 T(n)=7T(n/2)+Θ(n²),解为 Θ(n^lg7),小于三次方。
优化重点是减少递归分支;比较时仍需考虑额外内存和常数成本。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第4章 分治策略 · 查看原书依据
Instead of performing eight recursive multiplications of n/2 × n/2 matrices, Strassen’s algorithm performs only seven.
参考来源
- 位置:《算法导论(第4版)》第 4 章 4.2 节(`OEBPS/chapter004.xhtml`,文本字符 [20000, 25000))。
- 结论依据:原文给出七次子问题乘法、加减及初始化的二次成本,并据主定理得到渐近界。
- 原始内容:Instead of performing eight recursive multiplications of n /2 × n /2 matrices, Strassen’s algorithm performs only seven.