知识卡片

普通读书笔记卡 · 3683.a.4

带主元置换仍保持三次方耗时

理解等级:中级

LUP每轮额外扫描当前列并交换行,核心舒尔补更新仍由三重循环主导,因此总耗时Θ(n³),与无置换LU同阶。

选择主元改善可计算性和稳定性,渐近成本不升阶。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第28章 矩阵运算 · 查看原书依据

      Because of its triply nested loop structure, LUP-DECOMPOSITION has a running time of Θ(n3), which is the same as that of LU-DECOMPOSITION. Thus, pivoting costs at most a constant factor in time. Exercises 28.1-1 Solve the equation by using forward substitution.

    参考来源

    - 位置:《算法导论(第4版)》第28章《矩阵运算》(OEBPS/chapter028.xhtml,文本字符[20000,25000))。 - 结论依据:原文给出主元策略、求解成本或块矩阵复杂度归约,并明确前提条件。 - 原始内容:Because of its triply nested loop structure, LUP-D ECOMPOSITION has a running time of Θ( n 3 ), which is the same as that of LU-D ECOMPOSITION . Thus, pivoting costs at most a constant factor in time. Exercises 28.1-1 Solve the equation by using forward substitution.