这些嵌套循环的Big-O [英] Big-O of These Nested Loops
问题描述
我对Big-O领域还很陌生,所以请在这里忍受.我一直在尽可能地搜索它,但是我仍然需要大量的工作来完全理解它.
我在练习中遇到了嵌套循环的问题,没有任何解决方案,而且看起来很复杂.因此,我们将不胜感激.
I'm pretty new to the Big-O field, so bear with me here. I have been searching about it as much as I could but I still need a lot of work to fully understand it.
I came across these nested for loops in a practicing exercises and there wasn't any solutions and they seem complicated. So, any help would be appreciated.
int sum=0;
for(int i=0; i < n^2; i++) { // n+1
for(int j = n-1; j >= n-1-i; j–-) { // n(n+1)/2 ?
sum = i+j; // n(n+1)/2 ?
System.out.println(sum); // n(n+1)/2 ?
}
}
Big-O =?
int sum=0;
for(int i=1; i <= 2^n; i=i*2) { // log(n)
for(int j=0; j <= log(i); j++) { // log(n(n+1)/2) ?
sum = i+j; // log(n(n+1)/2) ?
System.out.println(sum); // log(n(n+1)/2) ?
}
}
Big-O =?
int sum = 0; int k = 23;
for(int i=k; i <= 2^(n−k); i=i*2) { // log(n)
for(int j=2^(i−k); j < 2^(i+k); j=j*2) { // log(log(n)) ?
sum = i+j; // log(log(n)) ?
System.out.println(sum); // log(log(n)) ?
}
}
Big-O =?
int sum=0;
for(int i=2n; i>=1; i=i/2) {
for(int j=i; j>=1; j=j/2) {
sum = i+j;
System.out.println(sum);
}
}
Big-O =?
-更正了#4.对不起,搞砸了.
-日志的基数为2.
-这里的 ^ 表示力量",而不是异或".
- Corrected #4. Sorry for the mess up.
- Base of the log is 2.
- The ^ here means "to the power", not xor.
推荐答案
还有很多问题,例如关于堆栈溢出的"Big-O嵌套循环" (和答案).
There are plenty questions like "Big-O of nested loops" here on stackoverflow (and answers).
但是,您会收到我的答复.但是首先存在一个符号问题:
您将此问题标记为java.在代码中,我看到类似2ⁿ
或n²
的内容.在 java中,这表示xor
,但是我想你的意思是Math.pow(2,n)
,因此对于此答案,我会将其视为幂运算符.
However, you will get an answer from me. But first there is a notation problem:
You tagged this question as java. In the code I see something like 2ⁿ
or n²
. In java this means xor
, but I think you meant Math.pow(2,n)
instead, so for this answer I will treat it as a power operator.
int sum=0;
for(int i=0; i < n^2; i++) { // outer loop
for(int j = n-1; j >= n-1-i; j–-) { // inner loop
sum = i+j; // inner operations
System.out.println(sum);
}
}
内部操作在O(1)
中运行,因此我只计算它们被调用的频率.
The inner operations runs in O(1)
, so I just counting how often they are called.
- 外部循环运行
n²
次.
对于每个 - 内部循环运行
i
次.
i
(来自外部循环),- The outer loop runs
n²
times. - for each
i
(from the outer loop) the inner loop runsi
times.
总共您得到0+1+...+(n²-1)+n² = n²(n²+1)/2
.在Θ(n⁴)
中.
int sum=0;
for(int i=1; i <= 2^n; i=i*2) { // outer loop
for(int j=0; j <= log(i); j++) { // inner loop
sum = i+j; // inner operations
System.out.println(sum);
}
}
- 外部循环运行
n
次,因为2⋅2⋅2⋅...⋅2
(n
次)等于2 n . - 假设对数的底数为2,则每个i = 2 k (1≤k≤n),内部循环运行
k
次. - The outer loop runs
n
times, since2⋅2⋅2⋅...⋅2
(n
times) equals 2n. - The inner loop runs
k
times for each i=2k (1 ≤ k ≤ n), assuming the base of the logarithm is 2.
总共您得到1+2+3+...+n-1+n = n(n+1)/2
.在Θ(n²)
中.
int sum = 0; int k = 23;
for(int i=k; i <= 2^(n−k); i=i*2) { // outer loop
for(int j=2^(i−k); j < 2^(i+k); j=j*2) { // inner loop
sum = i+j; // inner operations
System.out.println(sum);
}
}
- 外循环运行
m
次,且m
最小,以使k⋅2m > 2n-k
成立.可以写为k⋅2k⋅2m > 2n
.k
必须为正(否则,外部循环将永远运行).假定k
受O(n)
限制(canstants也位于O(n)
中),m
也受O(n)
限制. - 内部循环始终运行
2⋅k
次,无论i
或n
是什么.在O(1)
中表示常量k
,在O(n)
中表示常量k
以O(n)
为边界. - The outer loop runs
m
times withm
minimal such thatk⋅2m > 2n-k
holds. This can be written ask⋅2k⋅2m > 2n
.k
has to be positiv (otherwise the outer loop will run forever). Assumingk
is bounded byO(n)
(canstants are also inO(n)
),m
is also bounded byO(n)
. - The inner loop runs always
2⋅k
times, no matter whati
orn
is. This is inO(1)
for a constantk
and inO(n)
for ak
bounded byO(n)
.
在O(n)
中,对于常量k
,您将得到O(n)
;对于k
,您将得到O(n²)
.
In total you get O(n)
for a constant k
and O(n²)
for a k
in O(n)
.
int sum=0;
for(int i=2n; i>=1; i=i/2) { // outer loop
for(int j=i; j>=1; j=j/2) { // inner loop
sum = i+j; // inner operations
System.out.println(sum);
}
}
- 外循环运行情况
log(n)
就像情况2(反之亦然) - 内部循环运行
j
次(基本上)在1
和2n
之间每个2的幂. - The outer loop runs
log(n)
times just like in case 2 (the other way around) - The inner loop runs
j
times for (basicly) each power of 2 between1
and2n
.
假设n = 2k
(表示log(n) = k
),您总共得到了
2k+1+2k+2k-1+...+22+21+20=2k+2-1=4n-1
.因此,这在O(n)
中.这也适用于n而不是2的幂.
Assuming n = 2k
(means log(n) = k
) you get in total
2k+1+2k+2k-1+...+22+21+20=2k+2-1=4n-1
. So this in in O(n)
. This also holds for n not a power of 2.
这篇关于这些嵌套循环的Big-O的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!