知识卡片

普通读书笔记卡 · 3602

矩阵分块宜用索引视图

理解等级:中级

递归矩阵乘法只需记录子矩阵在原矩阵中的位置,就能以 Θ(1) 时间完成分块,并原地更新结果。

若复制各块,每层还要搬运 Θ(n²) 个元素。

二者在八路递归乘法中同为 Θ(n³),但实现代价不同;对递归矩阵加法,复制成本甚至会改变总复杂度。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第4章 分治策略 · 查看原书依据

      Partitioning a matrix (or recursively, a submatrix) only involves arithmetic on this location information, which has constant size independent of the size of the matrix.

    参考来源

    - 位置:《算法导论(第4版)》第 4 章 4.1 节(`OEBPS/chapter004.xhtml`,文本字符 [15000, 20000))。 - 结论依据:原文比较复制子矩阵与索引计算两种分块方式,并说明后一种只操作定长位置信息。 - 原始内容:Partitioning a matrix (or recursively, a submatrix) only involves arithmetic on this location information, which has constant size independent of the size of the matrix.