matrix - 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

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

    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) 中。 p>

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

当然，您可以高估大 oh 和低估大 omega:对于每种算法，您可以说它是 Ω(1)，对于某些算法，它是 O(2 ⁿ)，但关键是你不会用它买太多东西。