复杂的嵌套循环不断增长的内部循环 [英] complexity for a nested loop with growing internal loop
问题描述
我很困惑这片code和逻辑所用的时间复杂度找到它。
无效DOIT(INT N){
对于(INT K = 1; K< N,K * = 2){< ----我猜测这个运行O(logN)的
对于(INT J = 1; J< k; J + = 1){< ------我不知道这是如何一期工程。
}
}
}
我已经尝试解决它用手写出来。但是,我还是不明白。
感谢您的时间。
编辑:
添加一个问题吧。同样的概念,不同的格式。
无效DOIT(INT N){
INT J,K; //我最终得到这个答案是为O(n ^(N / 2)),但后来我被卡住后...是,即使是正确的答案?
为(K = 1; K&所述N / 2; K + = 1){
为(J = K表; J&2 * K; J + = 1)[
X [J] = X [J-K] + X [J]; //这其实并不重要
}
}
}
总的复杂性实际上是 O(N)
声明:对于每个 K
你有 K
内部循环迭代。 (说服自己为什么它是正确的)
表示总内部循环迭代通过数T(N)
,让外循环的次数是 ^ h
。
这意味着我们有:
T(N)= 1 + 2 + 4 + ...... + 2 ^ H
< 2 * 2 ^ H(1)
= 2 ^(H + 1)
= 2 ^(logN个+ 1)(2)
= 2 ^(日志(2N))
= 2N
(1)从总和或几何级数
(2)注意平等 2 ^(H + 1)= 2 ^(logN个+ 1)
是因为 H = logN个
,我们有(如你所说) logN个
外循环迭代。
I am confused to the time complexity of this piece of code and the logic used to find it.
void doit(int N) {
for (int k = 1; k < N; k *= 2) { <----I am guessing this runs O(logN)
for (int j = 1; j < k; j += 1) { <------I am not sure how this one works.
}
}
}
I have already tried solving it out by hand writing it out. But, I still don't understand it.
Thank you for your time.
EDIT:
Adding another question to it. Same concept, different format.
void doit(int N) {
int j, k; //I ended up getting this answer to be O(n^(n/2)) But then I was stuck after that...is that even the right answer?
for (k = 1; k < N / 2; k += 1) {
for (j = k; j < 2 * k; j += 1) [
x[j] = x[j-k] + x[j];//This doesn't really matter
}
}
}
The total complexity is actually O(N)
Claim: For each k
you have k
inner loop iterations. (convince yourself why it is correct)
Denote the number of total inner loops iterations by T(N)
, and let the number of outer loops be h
.
This means we have:
T(N) = 1 + 2 + 4 + ... + 2^h
< 2 * 2^h (1)
= 2^(h+1)
= 2^(logN + 1) (2)
= 2^(log(2N))
= 2N
(1) From sum or geometric series
(2) Note that the equality 2^(h+1) = 2^(logN + 1)
is because h = logN
, we have (as you said) logN
outer loop iterations.
这篇关于复杂的嵌套循环不断增长的内部循环的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!