知识卡片
矩阵乘法三重循环为立方界
稠密 n×n 矩阵乘法逐个计算 n² 个输出元素,每个元素累加 n 个乘积,因此三重循环耗时 Θ(n³)。
先把输出矩阵清零只需 Θ(n²),不改变总渐近界;后续分治算法应以这个基线比较。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第4章 分治策略 · 查看原书依据
Because each of the triply nested for loops runs for exactly n iterations, and each execution of line 4 takes constant time, the MATRIX-MULTIPLY procedure operates in Θ(n3) time.
参考来源
- 位置:《算法导论(第4版)》第 4 章 4.1 节“Multiplying square matrices”(`OEBPS/chapter004.xhtml`,文本字符 [10000, 15000),公式图 Art_P100)。
- 结论依据:原文的 MATRIX-MULTIPLY 伪代码有三个各执行 n 次的循环,并单独计算初始化成本。
- 原始内容:Because each of the triply nested for loops runs for exactly n iterations, and each execution of line 4 takes constant time, the M ATRIX -M ULTIPLY procedure operates in Θ( n 3 ) time.