确定这些不同循环的大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(登录)

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)为简单起见假设n = 3k,对于某些正整数k.

   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)为简单起见,假设n = k2,对于某些正整数k.

   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)为简单起见假设n = 2s,对于某些正整数s.

   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)为简单起见,假设n = 2s,对于某些正整数s.

  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

http://i.stack.imgur.com/zMkt7.jpg

• 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;

我的答案: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每次迭代都是三倍,因此它具有三个连续的幂.

循环显然每次迭代只做O(1)工作,所以这里的主要问题是将有多少次迭代.i> 时,循环将停止n.如果我们让k循环的任意迭代,ion迭代的值k将是3 ^k.当k> log ₃ n 时,循环在3 ^k > 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(登录)

不完全的.请注意,j仍然是线性增长,但环只要为J运行² ≤ñ.这意味着只要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 ^2开始,但请注意每次迭代时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)部分.

部分(m)

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 ³).但是,更仔细地查看内循环的迭代次数:

Ñ ³ + N ³ /2 +Ñ ³ /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),使用^{log _b c} = c ^{log _b a}的事实.这有帮助吗？

希望这可以帮助!