在对矩阵进行 O(n^2) 操作时将矩阵减半的时间复杂度是多少？

Question

假设您有两个方阵，m1 和 m2，大小为 n X n。该算法迭代地对它们运行 O(n^2) 操作，同时在每次迭代时将矩阵减半。类似于下面的伪代码：

while m1.width > 0:
    u = m1 & m2  # pairwise logical and operation (O(n^2))
    m1 = halve(m1)
    m2 = halve(m2)

由于循环重复 log(n) 次，O(n^2.log(n)) 是算法时间复杂度的上限。我正在寻找更严格的上限。有什么想法吗？

基于估计 O(n^2) 的矩阵大小呈对数收缩的前提，我希望有一个更严格的上限。

Answer 1

不清楚“减半”是什么，但假设它将 n 减半（而不是矩阵中的元素数量减半），此计算显示 O(n^2)： n^2 + (n/2)^2 + (n/4)^2 + ... = n^2 * (1 + 1/4 + 1/16 + ...) = 4n^ 2/3.

如果它将矩阵中的元素数量减半，那么您将进行以下计算（也给出 O(n^2)）： n^2 + n^2/2 + n^2/4 + ... = n^2(1 + 1/2 + 1/4 + 1/8 + ...) = 2n^2.

这里使用的常用技巧是计算减半算法的复杂性，将总和取无穷大而不是在 n/2^k 达到 1 时停止。这恰好给出了一个严格的上限。

Answer 2

对于这样的循环，将每次迭代中完成的工作相加通常是一个好主意，而不是将一次迭代完成的工作乘以迭代次数。毕竟，每次迭代完成的工作是变化的。

暂时不考虑 O 符号，您的第一次迭代大约做了 n^2 次工作，既计算 AND 又将矩阵大小减半。现在，第二次迭代做了多少工作？好吧，因为你的矩阵在每个维度上都是以前的一半，所以对它们所做的工作大约是 (n / 2)^2 = n^2 / 4。当你再次将矩阵减半时，下一个 AND 做 (n / 4)^2 = n^2 / 16 工作。更一般地说，第 k 次执行循环时，您的 AND 运算将完成 n^2 / 4^k 次工作。

将循环的所有迭代相加得到完成的总工作量是

n^2 / 4^0 + n^2 / 4^1 + n^2 / 4^2 + …

= n^2 · (1 / 4^0 + 1/4^1 + 1/4^2 + …)

后一位是几何级数之和，加起来是4/3。所以这给了我们完成的总工作量是我的 4n^2 / 3，即 O(n^2).

另一种理解方式：虽然您的代码是迭代编写的，但您可以将其想象成一个递归算法，它执行 O(n^2) 的工作，然后在大小为 n / 2 的输入上再次运行。这给出了复发

T(n) = T(n / 2) + O(n^2).

然后大定理告诉您（a = 1，b = 2，d = 2，并且 log_b a < d）解是 O(n^2)。

在对矩阵进行 O(n^2) 操作时将矩阵减半的时间复杂度是多少？

What is time complexity of halving a matrix while doing an O(n^2) operation on it?

algorithm

time-complexity