Big Oh、Big Omega 和 Theta 算法的计算复杂度

Question

我正在尝试解决以下有关计算复杂性的问题：

Compute the computational complexity of the following algorithm and write down its complexity in Big O, Big Omega and Theta
for i=1 to m {
   x(i) =0;
   for j=1 to n {
      x(i) = x(i) + A(i,j) * b(j)
   }
}
where A is mxn and b is nx1.

我得到了大 O O(mn^2) 大 Omega(1) 和 Theta(mn^2).

Answer 1

回想一下 f = Theta(g) 当且仅当 f=O(g) 和 f=Omega(g)。

矩阵向量乘积可以在 Theta(mn) 时间内计算（假设是简单的实现），向量的和在 O(m) 内计算，所以总运行时间是 Theta(mn).从这里可以看出时间也是 O(mn) 和 Omega(mn).

Answer 2

假设下面的语句在常数时间内运行：

    x(i) = x(i) + A(i,j) * b(j)

这是在 O(1) 中完成的，并且不依赖于 i 和 j 的值。由于您在内部 for 循环中迭代此语句，恰好 n 次，因此您可以说以下代码在 O(n) 中运行：

x(i) =0;
for j=1 to n {
    meth1
}

（假设赋值也是在恒定时间内完成的）。同样，它不依赖于 i 的确切值。最后我们考虑外循环：

for i=1 to m {
   meth2
}

方法 meth2 被精确重复 m 次，因此时间复杂度的严格上限为 O(n·m).

由于没有条件语句，也没有递归和数据结构A、b和x 不改变程序的执行，算法也是big Omega(m n)和big Theta(m n)。

当然你可以高估 big oh 而低估 big omega：对于每个算法你都可以说它是 Ω(1) 而对于某些算法它是 O(2ⁿ)，但关键是你买的东西不多。

Big Oh、Big Omega 和 Theta 算法的计算复杂度

Computational Complexity of Algorithm in Big Oh, Big Omega and Theta

complexity-theory

matrix