确定这些不同循环的big-O运行时? [英] Determining the big-O runtimes of these different loops?
问题描述
我有一系列问题需要反馈和答案.我将对我的想法发表评论，这不是家庭作业，而是考试的准备.
I have a series of questions in which I need feedback and answers. I will comment as to what I think, this is not a homework assignment but rather preparation for my exam.
我的主要问题是确定不同情况下循环的迭代.怎么去解决这个问题?
My main problem is determining the iterations of a loop for different cases. How would go about attempting to figure that out?
评估运行时间.
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)
对于以下以下问题，我没有正确的答案.
For the following Questions below, I do not have the correct answers.
Q3. 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)
b)为简单起见，假设n = 3 ^ k
b) Assume for simplicity that 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，
c) Assume for simplicity that 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)
My Answer: 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)
My Answer: O(n^4)
(g)为简单起见，假设对于某个正整数k，n = 3k.
(g) Assume for simplicity that n = 3k, for some positive integer 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(n x对数基数为3 n?)
My Answer: O (n x log base 3 n? )
(h)为简单起见，假设对于某个正整数k，n = k2.
(h) Assume for simplicity that n = k2, for some positive integer 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++;
我的答案:n x logn x log n = O(n log n ^ 2)
My Answer: n x logn x log n = O(n log n^2)
(i)为简单起见，假设对于某些正整数s，n = 2s.
(i) Assume for simplicity that n = 2s, for some positive integer 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)
My Answer: 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)
My Answer: O(n^3)
(k) int i = 1，z = 0； while(z< n *(n + 1)/2){//算术级数，运行n次 z + = i; i ++; }
(k) int i=1, z=0; while( z < n*(n+1)/2 ){ //arithmetic series, runs n times z+=i; i++; }
我的回答:O(n)
(m)为简单起见，假设对于某些正整数s，n = 2s.
(m) Assume for simplicity that n = 2s, for some positive integer 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)
My Answer: 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)不确定-我什至应该尝试这些吗?*
- a) True - since its bounded below by n^2
- b) False - f(n) not strictly smaller than g(n)
- c) True
- d) True -bounded by n^10
- e) False - f(n) not strictly smaller than g(n)
- f) True
- g) True
- h) false - since does not equal O(nlogn)
- i) true
- j) not sure
- k) not sure
- l) not sure - how should i even attempt these?*
谢谢.
推荐答案
让我们一次遍历这些内容.
Let's go through these one at a time.
int x=0; //constant
for(int i=4*n; i>=1; i--) //runs n times, disregard the constant
x=x+2*i;
我的回答:O(n)
My Answer: O(n)
是的！没错循环运行O(n)次，每次迭代执行O(1).
Yep! That's correct. The loop runs O(n) times and does O(1) work per iteration.
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)
My Answer: O(n)
不完全是.在循环进行时考虑i的值.它将采用一系列值1、3、9、27、81、243，...，3 k .由于i在每次迭代中都增加了三倍，因此需要连续三次幂.
Not quite. Think about the values of i as the loop progresses. It will take on the series of values 1, 3, 9, 27, 81, 243, ..., 3k. Since i is tripling on each iteration, it takes on successive powers of three.
该循环显然只在每次迭代中执行O(1)，因此这里的主要问题是总共将进行多少次迭代.当i> n时，循环将停止.如果让k为循环的任意迭代，则迭代k上i的值为3 k .当3 k > n时，循环停止，这在k> log 3 n时发生.因此，迭代次数仅为O(log n)，所以总复杂度为O(log n).
The loop clearly only does O(1) work per iteration, so the main question here is how many total iterations there will be. The loop will stop when i > n. If we let k be some arbitrary iteration of the loop, the value of i on iteration k will be 3k. The loop stops when 3k > n, which happens when k > log3 n. Therefore, the number of iterations is only O(log n), so the total complexity is O(log n).
int y=0;
for(int j=1; j*j<=n; j++) //runs O(logn)? j <= (n)^1/2
y++; //constant
我的回答:O(登录)
My Answer: O(logn)
不完全是.注意，j仍在线性增长，但是循环运行的时间与j 2 ≤相同. .这意味着，一旦j超过√ n，循环将停止.因此，该循环只有O(√ n)次迭代，并且由于每个迭代都执行O(1)工作，因此完成的总工作量为O(√ n).
Not quite. Notice that j is still growing linearly, but the loop runs as long as j2 ≤ n. This means that as soon as j exceeds √ n, the loop will stop. Therefore, there will only be O(√n) iterations of the loop, and since each one does O(1) work, the total work done is O(√n).
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)
My Answer: O(n^3)
不完全是.实际上，您实际上在重复计算很多需要做的工作.您是正确的，内循环将运行n +(n-1)+(n-2)+ ... + 1次，即O(n 2 )次，但是已经在外循环的所有迭代中进行了总结.您无需再将该值乘以O(n).最准确的答案是O(n 2 ).
Not quite. You're actually doubly-counting a lot of the work you need to do. You're correct that the inner loop will run n + (n-1) + (n-2) + ... + 1 times, which is O(n2) times, but you're already summing up across all iterations of the outer loop. You don't need to multiply that value by O(n) one more time. The most accurate answer would be O(n2).
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)
My Answer: O(n)
是的！完全正确.
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)
My Answer: O(n^4)
再说一次，我相信您是在高估.内部循环将运行0 + n + 2n + 3n + 4n + ... + n(n-1)= n(0 +1 + 2 + ... + n-1)次，因此总工作量为O(n 3 ).您不应该乘以外循环运行的次数，因为您已经在所有迭代中进行了总结.最准确的运行时应为O(n 3 ).
Again, I believe you're overcounting. The inner loop will run 0 + n + 2n + 3n + 4n + ... + n(n-1) = n(0 + 1 + 2 + ... + n - 1) times, so the total work done is O(n3). You shouldn't multiply by the number of times the outer loop runs because you're already summing up across all iterations. The most accurate runtime would be O(n3).
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对数基数为3 n?)
My Answer: O (n x log base 3 n? )
这里的外循环确实会运行O(log n)次，但是让我们看一下内循环会执行多少工作.您是正确的，if语句始终求值为true.这意味着内部循环将执行1 + 3 + 9 + 27 + ... + 3 log 3 n 的工作.但是，该总和为(3 log 3 n + 1 -1)/2 =(3n +1)/2.因此，此处要做的全部工作只是O(n).
The outer loop here will indeed run O(log n) times, but let's see how much work the inner loop does. You're correct that the if statement always evaluates to true. This means that the inner loop will do 1 + 3 + 9 + 27 + ... + 3log3 n work. This summation, however, works out to (3log3 n + 1 - 1) / 2 = (3n + 1) / 2. Therefore, the total work done here is just O(n).
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)
My Answer: n x logn x log n = O(n log n^2)
不完全是.看第二个循环.实际上，它使用与早期部分之一相同的逻辑来运行O(√ n)次.该第三个内部循环也运行O(√ n)次，因此完成的总工作量将为O(n 2 ).
Not quite. Look at the second loop. This actually runs O(√n) times using the same logic as one of the earlier parts. That third inner loop also runs O(√n) times, and so the total work done will be O(n2).
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)
My Answer: O(n^4)
不完全是.外循环以初始化为n 2 的k开始，但请注意，每次迭代将k减半.这意味着外循环的迭代次数将为log(n 2 )= 2 log n = O(log n)，因此外循环仅运行O(log n)次.该内部循环确实完成了O(n 2 )的工作，因此总运行时间为O(n 2 log n).
Not quite. The outer loop starts with k initialized to n2, but notice that k is halved on each iteration. This means that the number of iterations of the outer loop will be log (n2) = 2 log n = O(log n), so the outer loop runs only O(log n) times. That inner loop does do O(n2) work, so the total runtime is O(n2 log n).
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)
My Answer: O(n^3)
关闭，但不完全是！第一个循环在时间O(n)中运行，到完成时，j的值为Θ(n 2 ).这意味着第二个循环的运行时间为θ(n 2 )，因此花费的总时间为Θ(n 2 ).
Close, but not quite! The first loop runs in time O(n) and by the time it's done, the value of j is Θ(n2). This means that the second loop runs for time Θ(n2), so the total time spent is Θ(n2).
int i=1, z=0;
while( z < n*(n+1)/2 )//arithmetic series, runs n times
{
z+=i; i++;
}
我的回答:O(n)
My Answer: O(n)
是的！
这很奇怪，没有(l)部分.
That's odd, there is no part (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)
My Answer: O(n^3 log n)
关闭，但不完全是.您是对的，外循环运行O(log n)次，内循环在第一次迭代中执行O(n 3 ).但是，请仔细观察内部循环的迭代次数:
Close, but not quite. You're right that the outer loop runs O(log n) times and that the inner loop does O(n3) work on the first iteration. However, look at the number of iterations of the inner loop more closely:
n 3 + n 3 /2+ n 3 /4 + n 3 /8 + ..
n3 + n3 / 2+ n3 / 4 + n3 / 8 + ...
= n 3 (1 + 1/2 + 1/4 + 1/8 + ...)
= n3 (1 + 1/2 + 1/4 + 1/8 + ...)
≤ 2n 3
因此，即使有log n次迭代，此处完成的总工作量实际上仅为O(n 3 ).
So the total work done here is actually only O(n3), even though there are log n iterations.
除了以下这些，您的答案都是正确的:
Your answers are all correct except for these:
f)是
这实际上是错误的.左侧的表达式是
This is actually false. The expression on the left is
(3/2)n 3/2 + 5n 2 + lg n
(3/2)n3/2 + 5n2 + lg n
不是不是Ω(n 2 √ n)=Ω(n 5/2 )
which is not Ω(n2 √n) = Ω(n5/2)
对于(j)，请注意log n 6 = 6 log n.有帮助吗?
For (j), note that log n6 = 6 log n. Does that help?
对于(k)，请问双方是否都是O和Ω彼此.你发现什么?
For (k), ask whether both sides are O and Ω of one another. What do you find?
对于(l)，使用a log b c = c log b a 的事实.有帮助吗?
For (l), use the fact that alogb c = clogba. Does that help?
希望这会有所帮助！
这篇关于确定这些不同循环的big-O运行时?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
