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(n x 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++;

我的答案:n x 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) 真 - 以 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;

My Answer: 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;
}

My Answer: O(n)

不完全的。想想 i 的值随着循环的进行。它将采用一系列值 1, 3, 9, 27, 81, 243, ..., 3k。自 i在每次迭代中增加三倍，它采用连续的 3 次幂。

循环显然每次迭代只执行 O(1) 工作，所以这里的主要问题是总共有多少次迭代。当 i 时循环将停止> n .如果我们让 k是循环的任意迭代， i 的值关于迭代 k将是 3k。当 3k > n 时循环停止，当 k > log3 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

My Answer: O(logn)

不完全的。请注意 j仍在线性增长，但只要 j2 ≤ 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;

My Answer: O(n^3)

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

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

My Answer: 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;

My Answer: O(n^4)

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

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

My Answer: O (n x log base 3 n? )

这里的外循环确实会运行 O(log n) 次，但让我们看看内循环做了多少工作。您是对的 if语句总是评估为真。这意味着内循环会做 1 + 3 + 9 + 27 + ... + 3log3 n 的工作。然而，这个总和的结果是 (3log3 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++;

My Answer: n x logn x log n = O(n log n^2)

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

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

My Answer: O(n^4)

不完全的。外循环以初始化为 n2 的 k 开始，但请注意，每次迭代时 k 减半。这意味着外循环的迭代次数将为 log (n2) = 2 log n = O(log n)，因此外循环仅运行 O(log n) 次。该内部循环确实执行 O(n2) 工作，因此总运行时间为 O(n2 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++;

My Answer: O(n^3)

接近，但不完全!第一个循环在 O(n) 时间内运行，当它完成时，j 的值是 Θ(n2)。这意味着第二个循环运行时间为 Θ(n2)，所以总时间为 Θ(n2)。

第 (k) 部分

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

My Answer: 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; 
}

My Answer: O(n^3 log n)

关闭，但不完全。你是对的，外循环运行 O(log n) 次，内循环在第一次迭代时执行 O(n3) 工作。但是，更仔细地查看内部循环的迭代次数:

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

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

≤ 2n³

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

问题 4

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

f) True

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

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

这是 不是 Ω(n2 √n) = Ω(n5/2)

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

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

对于 (l)，使用 alogb c = clogba 的事实。这有帮助吗？

希望这可以帮助!