我有一系列的，我需要的反馈和解答。我会什么，我想发表评论，这不是一个家庭作业，而是准备我的考试。

我的主要问题是确定不同的情况下，循环迭代。怎么会去尝试明白这一点？

评估运行时间。

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×N 2×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-1K-

    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）

（克）假设为简单起见为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底数3 N 2）

（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日志N = O（N日志N ^ 2）

（ⅰ）假设为简单起见为n = 2秒，对于一些正整数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; 而（Z <N *（N + 1）/ 2）{//算术系列，运行n倍Z + = I; 我++; }

我的回答：O（N）

（M）假设为简单起见为n = 2秒，对于一些正整数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）真-bounded用n ^ 10
E）假 - F（N）不严格小于g时（n）的
F）真
G）真
1H）假 - 因为不等于O（nlogn）
我）真
j）的不确定
K）不知道
L）不知道 - 我应该如何甚至企图这些*

提前致谢。

让我们通过这些一次一个。

第（一）

 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是循环的一些任意迭代，值了i的迭代k将是3 ^K。循环停止时3 ^K> N，这恰好当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（LOGN）

不完全的。请注意， j仍在线性增长，但环只要运行为J ^2≤ñ。这意味着，只要j超过√不适用，循环就会停止。因此，将仅存在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 ^2）次，但你已经在所有的迭代总结的外部循环。你并不需要乘以O（n）的该值一次。最准确的答案将是O（N ^2）。

部分（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 ^3）。你不应该由外部循环运行，因为你已经在所有的迭代总结的次数相乘。最准确的运行时间将是O（N ^3）。

部分（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底数3 N 2）

外环这里确实会运行O（log n）的时间，但让我们来看看内环多少工作呢。你是正确的，因为if语句总是判断为真。这意味着内部循环会做1 + 3 + 9 + 27 + ... + 3 ^{原木₃ N}功。这个总和，但工程以（3 ^{原木₃ N + 1} - 1）/ 2 =（N + 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日志N = O（N日志N ^ 2）

不完全的。再看第二个循环。这实际上使用相同的逻辑作为较早部分中的一个上运行O（√N）次。该第三内环还运行O（√N）倍，所以所做的总功将是为O（n ^2）。

部分（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被在每次迭代减半。这意味着，外循环的迭代数目将是登录（N ^2）= 2个对数N = O（log n）的，所以外部循环运行只O（log n）的时间。这内环并做O（N ^2）工作，所以总运行时间为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 ^2）。这意味着，第二环路时间Θ（N ^2），因此所花费的总时间为Θ（n ^2）的运行。

部分（K）

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

我的回答：O（N）

这是正确的！

部（S）

这很奇怪，没有部件（1）。

部分（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 ^3）在第一次迭代工作。然而，看看内部循环的迭代次数更加紧密：

N ³ + N ^3/2 + N ^3/4 + N ^3/8 + ...
= N ^3（1 + 1/2 1/4 + 1/8 + + ...）
≤2N ³

所以在这里所做的总功实际上只有O（N ^3），即使有日志n次迭代。

问题4

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

F）真

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

（3/2）N ^3/2 + 5N ² + LGÑ

这是不 Ω（N ^{2√N）=Ω（N} ^5/2）

对于（j）中，注意，日志N ⁶ = 6为log N。这是否帮助？

其中（k），要求双方是否O和彼此的Ω。你发现了什么？

为（L），可以使用以下事实：一个^{日志_B C} = C ^{日志_B A。} 这是否帮助？

希望这可以帮助！

确定这些不同的环路的大O的运行时间？(Determining the big-O runtimes

Answer 1:

第（一）

（b）部分

（c）部分

部分（d）

部分（e）

部分（f）

部分（G）

（H）部分

部分（I）

部分（J）

部分（K）

部（S）

部分（M）

问题4

收藏的人(0)

确定这些不同的环路的大O的运行时间？(Determining the big-O runtimes

Answer 1:

第（一）

（b）部分

（c）部分

部分（d）

部分（e）

部分（f）

部分（G）

（H）部分

部分（I）

部分（J）

部分（K）

部（S）

部分（M）

问题4

收藏的人(0)

举报内容

检举类型

检举原因

检举说明(必填)

打开微信“扫一扫”，打开网页后点击屏幕右上角分享按钮