0

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

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();
}

提前致谢

4

3 回答 3

2

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

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();

被调用 whilei <= 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，第二次被调用，以此类推，直到它2n-1等于n + (n-1)。所以我们得到一个这样的序列{n+1, n+2, n+3, ... , n+(n-1)}。

如果我们对序列求和，我们会得到n-1timesn和 sum 1+2+3+...+ (n-1)。最后一个术语可以用“Gaußsche Summenformel”解决（对不起，我没有它的英文名称，但你可以在德语 wiki 链接中看到公式）所以它等于((n-1)*n)/2

所以第一项是(n-1) * n + ((n-1)*n)/2 *D

最后一项是 if 语句，它被称为，执行 If 语句的时间在2*n*I哪里。I

于 2013-01-10T12:08:59.457 回答
1

好吧，这里的问题是，对于所有三个循环结构，迭代次数如何与 成比例变化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 子句在恒定时间内运行，因此整个循环在 中O(n * log_2(n))，假设它doSomething()也在恒定时间内。

这是否使它更清楚？:)

于 2013-01-08T13:12:08.077 回答
1

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

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

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

在评论中，我忘了添加我定义n=200的 .

解释

我们可以说，虽然j在迭代中的每一步都有规律地递增，但它永远不会超过n. 为什么？n迭代后， j==n. 递增后将0在语句中设置为。语句中,将递增次，第 th 次递增。这一切重新开始，直到。j %= n ii += j / ni0 n-1n1i >= n

于 2013-01-08T13:16:07.783 回答