知识卡片
矩阵分块宜用索引视图
递归矩阵乘法只需记录子矩阵在原矩阵中的位置,就能以 Θ(1) 时间完成分块,并原地更新结果。
若复制各块,每层还要搬运 Θ(n²) 个元素。
二者在八路递归乘法中同为 Θ(n³),但实现代价不同;对递归矩阵加法,复制成本甚至会改变总复杂度。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 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.