algorithm - 确定这些不同循环的大 O 运行时？

Question

我有一系列问题需要反馈和答案。我将评论我的想法，这不是家庭作业，而是为我的考试做准备。

我的主要问题是确定不同情况下循环的迭代。将如何尝试解决这个问题？

评估运行时间。

Q2。

 for(int i =0 ; i < =n ; i++) // runs n times
   for(int j =1; j<= i * i; j++) // same reasoning as 1. n^2
      if (j % i == 0)
         for(int k = 0; k<j; k++) // runs n^2 times? <- same reasoning as above.
            sum++;

正确答案：N × N2 × N = O(N^4)

对于以下以下问题，我没有正确答案。

Q3。一个）

     int x=0; //constant
     for(int i=4*n; i>=1; i--) //runs n times, disregard the constant
         x=x+2*i;

我的答案：O(n)

b) 为简单起见，假设 n = 3^k

    int z=0;
    int x=0;
    for (int i=1; i<=n; i=i*3){ // runs n/3 times? how does it effect final answer?
       z = z+5;
       z++;
       x = 2*x;
    }

我的答案：O(n)

c) 为简单起见，假设 n = k^2，

   int y=0; 
   for(int j=1; j*j<=n; j++) //runs O(logn)?  j <= (n)^1/2
   y++; //constant

我的答案：O(logn)

d)

  int b=0; //constant
  for(int i=n; i>0; i--) //n times
    for(int j=0; j<i; j++) // runs n+ n-1 +...+ 1. O(n^2) 
      b=b+5;

我的答案：O(n^3)

(e)

 int y=1;
 int j=0;
 for(j=1; j<=2n; j=j+2) //runs n times
    y=y+i;
 int s=0;
 for(i=1; i<=j; i++) // runs n times
 s++;

我的答案：O(n)

（F）

 int b=0;
 for(int i=0; i<n; i++) //runs n times
   for(int j=0; j<i*n; j++) //runs n^2 x n times? 
      b=b+5;

我的答案：O(n^4)

(g) 为简单起见，假设对于某个正整数 k，n = 3k。

   int x=0;
   for(int i=1; i<=n; i=i*3){  //runs 1, 3, 9, 27...for values of i. 
     if(i%2 != 0) //will always be true for values above
      for(int j=0; j<i; j++) // runs n times
        x++;
    }

我的答案：O (nx log base 3 n?)

(h) 为简单起见，对于某个正整数 k，假设 n = k2。

   int t=0;
   for(int i=1; i<=n; i++) //runs n times
      for(int j=0; j*j<4*n; j++) //runs O(logn)
         for(int k=1; k*k<=9*n; k++) //runs O(logn)
            t++;

我的答案：nx logn x log n = O(n log n^2)

(i) 为简单起见，对于某些正整数 s，假设 n = 2s。

   int a = 0;
   int k = n*n;
     while(k > 1) //runs n^2
     {
       for (int j=0; j<n*n; j++) //runs n^2
          { a++; }
        k = k/2;
    }

我的答案：O(n^4)

(j)

  int i=0, j=0, y=0, s=0;
  for(j=0; j<n+1; j++) //runs n times
     y=y+j; //y equals n(n+1)/2 ~ O(n^2)
  for(i=1; i<=y; i++) // runs n^2 times
     s++;

我的答案：O(n^3)

(k) int i=1，z=0；while( z < n*(n+1)/2 ){ //算术级数，运行 n 次 z+=i; 我++；}

我的答案：O(n)

(m) 为简单起见，对于某些正整数 s，假设 n = 2s。

  int a = 0;
  int k = n*n*n;
  while(k > 1) //runs O(logn) complexity
   {
     for (int j=0; j<k; j++) //runs n^3 times
      { a--; }
     k = k/2; 
    }

我的答案：O(n^3 log n)

问题 4

• a) 真 - 因为它的下界为 n^2
• b) 错误 - f(n) 不严格小于 g(n)
• c) 对
• d) True 以 n^10 为界
• e) 错误 - f(n) 不严格小于 g(n)
• f) 对
• g) 对
• h) false - 因为不等于 O(nlogn)
• i) 真的
• j) 不确定
• k) 不确定
• l) 不确定 - 我应该如何尝试这些？*

提前致谢。

Answer 1

让我们一次过一遍。

(a) 部分

 int x=0; //constant
 for(int i=4*n; i>=1; i--) //runs n times, disregard the constant
     x=x+2*i;

我的答案：O(n)

是的！这是正确的。循环运行 O(n) 次，每次迭代执行 O(1) 次。

(b) 部分

int z=0;
int x=0;
for (int i=1; i<=n; i=i*3){ // runs n/3 times? how does it effect final answer?
   z = z+5;
   z++;
   x = 2*x;
}

我的答案：O(n)

不完全的。i随着循环的进行，想想 的值。它将采用一系列值 1, 3, 9, 27, 81, 243, ..., 3 ^k。由于i每次迭代都是三倍，因此它采用连续的 3 次方。

循环显然每次迭代只做 O(1) 工作，所以这里的主要问题是总共有多少次迭代。当i>时，循环将停止n。如果我们让k循环的一些任意迭代，迭代的值i将k是 3 ^k。^{循环在 3 k} > n时停止，这发生在 k > log ₃ n 时。因此，迭代次数仅为O(log n)，因此总复杂度为O(log n)。

(c) 部分

int y=0; 
for(int j=1; j*j<=n; j++) //runs O(logn)?  j <= (n)^1/2
    y++; //constant

我的答案：O(logn)

不完全的。请注意，j它仍在线性增长，但只要 j ² ≤ n，循环就会运行。这意味着只要 j 超过√ n，循环就会停止。因此，循环只会有 O(√n) 次迭代，并且由于每一次都做 O(1) 次工作，所以完成的总工作量是 O(√n)。

(d) 部分

int b=0; //constant
for(int i=n; i>0; i--) //n times
   for(int j=0; j<i; j++) // runs n+ n-1 +...+ 1. O(n^2) 
      b=b+5;

我的答案：O(n^3)

不完全的。你实际上是在加倍计算你需要做的很多工作。您是正确的，内部循环将运行 n + (n-1) + (n-2) + ... + 1 次，即 O(n ² ) 次，但是您已经对所有迭代进行了总结的外循环。您不需要再将该值乘以 O(n) 一次。最准确的答案是 O(n ² )。

(e) 部分

int y=1;
int j=0;
for(j=1; j<=2n; j=j+2) //runs n times
   y=y+i;

int s=0;
for(i=1; i<=j; i++) // runs n times
   s++;

我的答案：O(n)

是的！非常正确。

(f) 部分

int b=0;
for(int i=0; i<n; i++) //runs n times
    for(int j=0; j<i*n; j++) //runs n^2 x n times? 
       b=b+5;

我的答案：O(n^4)

再说一次，我相信你多算了。内部循环将运行 0 + n + 2n + 3n + 4n + ... + n(n-1) = n(0 + 1 + 2 + ... + n - 1) 次，所以完成的总工作是O(n ³ )。您不应该乘以外部循环运行的次数，因为您已经对所有迭代进行了总结。最准确的运行时间是 O(n ³ )。

(g) 部分

int x=0;
for(int i=1; i<=n; i=i*3){  //runs 1, 3, 9, 27...for values of i. 
   if(i%2 != 0) //will always be true for values above
      for(int j=0; j<i; j++) // runs n times
         x++;
 }

我的答案：O (nx log base 3 n?)

这里的外循环确实会运行 O(log n) 次，但让我们看看内循环做了多少工作。您是正确的，该if语句始终评估为真。这意味着内部循环将执行 1 + 3 + 9 + 27 + ... + 3 ^{log ₃ n}工作。然而，这个总和结果为 (3 ^{log ₃ n + 1} - 1) / 2 = (3n + 1) / 2。因此，这里完成的总工作量仅为 O(n)。

(h) 部分

int t=0;
for(int i=1; i<=n; i++) //runs n times
   for(int j=0; j*j<4*n; j++) //runs O(logn)
      for(int k=1; k*k<=9*n; k++) //runs O(logn)
         t++;

我的答案：nx logn x log n = O(n log n^2)

不完全的。看第二个循环。这实际上使用与前面部分之一相同的逻辑运行 O(√n) 次。第三个内部循环也运行 O(√n) 次，因此完成的总工作量将是 O(n ² )。

第 (i) 部分

int a = 0;
int k = n*n;
while(k > 1) //runs n^2
{
    for (int j=0; j<n*n; j++) //runs n^2
       { a++; }
     k = k/2;
}

我的答案：O(n^4)

不完全的。外部循环以 k 初始化为 n ²开始，但请注意 k 在每次迭代中减半。这意味着外循环的迭代次数将为 log (n ² ) = 2 log n = O(log n)，因此外循环仅运行 O(log n) 次。该内部循环确实完成了 O(n ² ) 的工作，因此总运行时间为 O(n ² log n)。

(j) 部分

int i=0, j=0, y=0, s=0;
for(j=0; j<n+1; j++) //runs n times
   y=y+j; //y equals n(n+1)/2 ~ O(n^2)
for(i=1; i<=y; i++) // runs n^2 times
   s++;

我的答案：O(n^3)

关闭，但不完全！第一个循环在 O(n) 时间内运行，当它完成时，j 的值是 Θ(n ² )。这意味着第二个循环的运行时间为 Θ(n ² )，因此花费的总时间为 Θ(n ² )。

(k) 部分

 int i=1, z=0;
 while( z < n*(n+1)/2 )//arithmetic series, runs n times
 {
       z+=i; i++;
 }

我的答案：O(n)

这是正确的！

(l) 部分

这很奇怪，没有部分（l）。

部分（米）

int a = 0;
int k = n*n*n;
while(k > 1) //runs O(logn) complexity
{
   for (int j=0; j<k; j++) //runs n^3 times
   { a--; }
   k = k/2; 
}

我的答案：O(n^3 log n)

关闭，但不完全。没错，外循环运行 O(log n) 次，而内循环在第一次迭代中运行 O(n ^{3 )。}但是，更仔细地查看内部循环的迭代次数：

n ³ + n ³ / 2+ n ³ / 4 + n ³ / 8 + ...

= n ³ (1 + 1/2 + 1/4 + 1/8 + ...)

≤ 2n ³

所以这里完成的总工作实际上只有 O(n ³ )，即使有 log n 次迭代。

问题 4

你的答案都是正确的，除了这些：

f) 对

这实际上是错误的。左边的表达式是

(3/2)n ^3/2 + 5n ² + lg n

不是Ω(n ² √n ) = Ω(n ^5/2 )

对于 (j)，请注意 log n ⁶ = 6 log n。这有帮助吗？

对于 (k)，询问双方是否是彼此的 O 和 Ω。你发现了什么？

^{对于 (l)，使用 a log _b c} = c ^{log _b a}的事实。这有帮助吗？

希望这可以帮助！