知识卡片

普通读书笔记卡 · 3602.a.1

少一次乘法可改变指数

理解等级:中级

Strassen 用 7 次而非 8 次半规模矩阵乘法,换取常数次矩阵加减。

加减只需 Θ(n²),形成 T(n)=7T(n/2)+Θ(n²),解为 Θ(n^lg7),小于三次方。

优化重点是减少递归分支;比较时仍需考虑额外内存和常数成本。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第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.