知识卡片

普通读书笔记卡 · 3601

矩阵乘法三重循环为立方界

理解等级:初级

稠密 n×n 矩阵乘法逐个计算 n² 个输出元素,每个元素累加 n 个乘积,因此三重循环耗时 Θ(n³)。

先把输出矩阵清零只需 Θ(n²),不改变总渐近界;后续分治算法应以这个基线比较。

这张卡片看不懂?

已有反馈 · 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.