C循环复杂度

Question

我正在准备考试，这些是去年考试中的一些问题。任务是计算精确复杂度和渐近复杂度。你会怎么解决这个问题？如果可能的话，是通用的。

for ( i = j = 0; i < n; j ++ ) {
  doSomething ();
  i += j / n;
  j %= n;
}

for ( i = 0; i < 2 * n; i += 2 )
  for ( j = 1; j <= n; j <<= 1 )
    if ( j & i )
      doSomething ();

for (i = 0; i < 2*n; i++) {
  if ( i > n )
    for (j = i; j < 2 * i; j ++ ) doSomething();
  else
    for (j = n; j < 2 * n; j ++ ) doSomething();
}

提前感谢

Answer 1

我对第三个循环的解决方案是

t(n) = [ (n-1)*n +  ((n-1)*n)/2 ] *D  + [ n^2 +n ] *D + [ 2n ]*I

在O(n^2)中也是如此，因为doSomething()有一个恒定的时间，并且i和j是整数。

第二个术语( [ n^2 +n ] *D )相当简单。

循环

for (j = n; j < 2 * n; j ++ ) doSomething();

在i <= n时调用，因此它将被调用n+1次，因为它从0开始。

循环for (j = n; j < 2 * n; j ++ )调用doSomething() n次，所以我们有(n+1)*n*D = [n^2+n] *D。我假设doSomething()有一个等于D的恒定时间

第一项有点复杂。

for (j = i; j < 2 * i; j ++ ) doSomething();

在i>n时调用，因此它将被调用n-1次。循环调用doSomething() i次。第一次调用n+1，第二次调用´n+2´，依此类推，直到2n-1等于n + (n-1)。所以我们得到一个类似于这个{n+1, n+2, n+3, ... , n+(n-1)}的序列。

如果我们把这个序列相加，我们得到n-1乘以n和和1+2+3+...+ (n-1)。最后一项可以用"Gaußsche Summenformel"解决(对不起，我没有它的英文名称，但你可以在德语维基链接中看到公式)，所以它等于((n-1)*n)/2

所以第一个术语是(n-1) * n + ((n-1)*n)/2 *D

最后一项是if语句，称为2*n*I，其中I是执行If语句的时间。

Answer 2

那么，这里的问题是，对于所有三个循环结构，迭代的数量是如何与n成比例变化的，对吧？那么让我们来看一下循环。我将省略第一个，因为你已经解决了它。

for ( i = 0; i < 2 * n; i += 2 )
  for ( j = 1; j <= n; j <<= 1 )
    if ( j & i )
      doSomething ();

很明显，外部的for循环恰好运行n次。内部循环运行log_2(n)次，因为是按位移位操作。if子句在固定时间内运行，因此假设doSomething()也在固定时间内，整个循环都在O(n * log_2(n))中。

这会让它更清晰吗？:)

Answer 3

根据请求，我将解释我是如何得出第一个循环等于如下结构的结果的：

int i, j;
for (i=0; i < n; i++) {
    for (j=0; j <= n; j++) {
        doSomething();
    }
}

首先，我必须承认，在我真正考虑它之前，我只是编写了一个小示例程序，其中包括在迭代期间打印i和j的三个for循环中的第一个。在我看到结果后，我在想为什么结果是这样的。

在注释中，我忘了加上我定义了n=200。

解释

我们可以说，尽管j在迭代中的每一步都会定期递增，但它永远不会超过n的值。为什么？在n迭代之后，j==n。在 i递增后，它将在j %= n 语句中设置为0。在语句i += j / n中，i将按0 n-1次递增，在第n次，它将按1递增。这一切都会重新开始，直到i >= n。