计算嵌套循环的大O [英] Calculating Big O for nested loops

问题描述

我在计算以下代码的大O时遇到问题。我从来都不是最聪明的饼干。 有谁能解释一下吗。由于嵌套循环，我在这里的猜测是O(N^2)，但我知道还有更多原因。

static inline int f1 (int a, int b)
{
 for (int c = 0; c < b; c++)
 {
   a -= n;
 }
 return a;
}

int f2 (int n) 
{
  int r = n * n * n;
  for (double i = n; i >= 0; i -= 2)
  {
     r = f1(r, i);
  }
  return r;
}

推荐答案

首先，请注意F1的运行时完全依赖于第二个参数，该参数控制循环迭代的次数。因此，它的运行时在第二个参数中是线性的。

接下来，注意f2中的循环运行n/2次，其中i取值0、2、4、6、...、n。因为i是f1的第二个参数，所以运行时间由

给出

0+2+4+...+n

=2(0+1+2+.+n)

=2&theta；(n^2)

=&Theta；(n^2)

所以运行时是&theta；(n^2)。请注意，几乎所有其他事情都是为了让你分心，意在误导你。只关注控制迭代和循环的变量会揭示您需要关注的实际逻辑。

希望这能有所帮助！

这篇关于计算嵌套循环的大O的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！