我对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.
内部操作在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 runs i 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, since 2⋅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.
- 外循环运行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 with m minimal such that k⋅2m > 2n-k holds. This can be written as k⋅2k⋅2m > 2n. k has to be positiv (otherwise the outer loop will run forever). Assuming k is bounded by O(n) (canstants are also in O(n)), m is also bounded by O(n).
- The inner loop runs always 2⋅k times, no matter what i or n is. This is in O(1) for a constant k and in O(n) for a k bounded by O(n).
- 外循环运行情况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 between 1 and 2n.
总共您得到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); } }
在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); } }
假设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
发布评论