gpt4 book ai didi

algorithm - 两个不等维矩阵相乘的时间复杂度是多少?

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:26:36 26 4
gpt4 key购买 nike

我研究了两个 n × n 矩阵相乘的大 O 复杂度,这需要时间 O(n3)。但是,将两个维度为 m × n 和 n × r 的矩形矩阵相乘时,如何获得大 O 复杂度呢?有人告诉我答案是 O(mnr),但我不确定这是从哪里来的。谁能解释一下?

谢谢!

最佳答案

我假设您正在谈论将两个 n × n 维方阵相乘的复杂度计算为 O(n3),并且正在询问将 m × n 矩阵相乘的复杂度和一个 n × r 矩阵。有专门的算法可以比简单的方法更快地解决这个问题,但出于这个问题的目的,我将只讨论标准的“将每个条目的每一行乘以每一列”算法。

首先,让我们看看 O(n3) 项在两个 n × n 矩阵相乘时的来源。请注意,对于结果矩阵的每个值,位置 (i, j) 的条目由左矩阵的第 i 行和右矩阵的第 j 列的内积给出。每行和每列都有 n 个元素,因此计算每个元素需要时间 Θ(n)。这样做 Θ(n2) 次(对结果矩阵的每个元素一次)需要时间 Θ(n3)。

现在在 m × n 矩阵和 n × r 矩阵的乘积的上下文中考虑这个问题。矩阵中的条目 (i, j) 由左矩阵的第 i 行(有 n 个条目)和右矩阵的第 j 列(有 n 个条目)的内积给出,因此计算它需要时间 Θ (n).您对结果矩阵的每个元素执行一次此操作。由于生成的矩阵的维度为 m × r,因此需要考虑 Θ(mr) 个元素。因此,完成的总功为 Θ(mnr)。

希望这对您有所帮助!

关于algorithm - 两个不等维矩阵相乘的时间复杂度是多少?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19508022/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com