Another Big O notation question...What is the Big O for the folling code:
另一个大O符号问题...对于代码的大O是什么：
for (int i = n; i > 0; i = i / 2){
for (int j = 0; j < n; j++){
for (int k = 0; k < n; k++){
count++;
}
}
}
My Thoughts: So breaking it down, I think the outside loop is O(log2(n)), then each of the inner loops is O(n) which would result in O(n^2 * log2(n)) Question #1 is that correct?
我的想法：所以打破它，我认为外部循环是O（log2（n）），然后每个内部循环是O（n），这将导致O（n ^ 2 * log2（n））问题＃ 1是正确的吗？
Question #2: when combining nested loops is it always just as simple as mulitply the Big O of each loop?
问题2：当组合嵌套循环时，它总是像每个循环的大O一样简单吗？
4 个解决方案
#1
10
When loop counters do not depend on one another, it's always possible to work from the inside outward.
当循环计数器不相互依赖时，它总是可以从内向外工作。
The innermost loop always takes time O(n), because it loops n times regardless of the values of j and i.
最内层循环总是花费时间O（n），因为无论j和i的值如何，它都会循环n次。
When the second loop runs, it runs for O(n) iterations, on each iteration doing O(n) work to run the innermost loop. This takes time O(n2).
当第二个循环运行时，它运行O（n）次迭代，在每次迭代时执行O（n）工作以运行最内层循环。这需要时间O（n2）。
Finally, when the outer loop runs, it does O(n2) work per iteration. It also runs for O(log n) iterations, since it runs equal to the number of times you have to divide n by two before you reach 1. Consequently, the total work is O(n2 log n).
最后，当外循环运行时，它每次迭代都会执行O（n2）工作。它也运行O（log n）次迭代，因为它的运行时间等于在达到1之前必须将n除以2的次数。因此，总工作量为O（n2 log n）。
In general, you cannot just multiply loops together, since their bounds might depend on one another. In this case, though, since there is no dependency, the runtimes can just be multiplied. Hopefully the above reasoning sheds some light on why this is - it's because if you work from the inside out thinking about how much work each loop does and how many times it does it, the runtimes end up getting multiplied together.
通常，您不能将循环相乘，因为它们的边界可能相互依赖。但是，在这种情况下，由于没有依赖性，运行时可以成倍增加。希望上面的推理能够解释为什么会这样 - 这是因为如果你从内到外思考每个循环做了多少工作以及它做了多少次，那么运行时最终会成倍增加。
Hope this helps!
希望这可以帮助！
#2
2
- Yes, this is correct: the outer loop is
logN, the other two areNeach, for the total ofO(N^2*LogN) - 是的，这是正确的：外部循环是logN，另外两个是N，每个都是O（N ^ 2 * LogN）
- In the simple cases, yes. In more complex cases, when loop indexes start at numbers indicated by other indexes, the calculations are more complex.
- 在简单的情况下，是的。在更复杂的情况下，当循环索引从其他索引指示的数字开始时，计算更复杂。
#3
2
To answer this slightly (note: slightly) more formally, say T(n) is the time (or number of operations) required to complete the algorithm. Then, for the outer loop, T(n) = log n*T2(n), where T2(n) is the number of operations inside the loop (ignoring any constants). Similarly, T2(n) = n*T3(n) = n*n.
为了更正式地回答这个问题（注意：稍微），说T（n）是完成算法所需的时间（或操作次数）。然后，对于外循环，T（n）= log n * T2（n），其中T2（n）是循环内的操作数（忽略任何常数）。类似地，T2（n）= n * T3（n）= n * n。
Then, use the following theorem:
然后，使用以下定理：
If f1(n) = O(g1(n)) and f2(n) = O(g2(n)), then f1(n)×f2(n) = O(g1(n)×g2(n))
(source and proof)如果f1（n）= O（g1（n））且f2（n）= O（g2（n）），则f1（n）×f2（n）= O（g1（n）×g2（n）） （来源和证明）
This leaves us with T(n) = O(n2logn).
这使我们得到T（n）= O（n2logn）。
"Combining nested loops" is just an application of this theorem. The trouble can be in figuring out exactly how many operations each loop uses, which in this case is simple.
“组合嵌套循环”只是该定理的一个应用。问题在于确定每个循环使用的确切操作数量，在这种情况下很简单。
#4
0
You can proceed formally using Sigma Notation, to faithfully imitate your loops:
您可以正式使用Sigma Notation，忠实地模仿您的循环：
#1
10
When loop counters do not depend on one another, it's always possible to work from the inside outward.
当循环计数器不相互依赖时，它总是可以从内向外工作。
The innermost loop always takes time O(n), because it loops n times regardless of the values of j and i.
最内层循环总是花费时间O（n），因为无论j和i的值如何，它都会循环n次。
When the second loop runs, it runs for O(n) iterations, on each iteration doing O(n) work to run the innermost loop. This takes time O(n2).
当第二个循环运行时，它运行O（n）次迭代，在每次迭代时执行O（n）工作以运行最内层循环。这需要时间O（n2）。
Finally, when the outer loop runs, it does O(n2) work per iteration. It also runs for O(log n) iterations, since it runs equal to the number of times you have to divide n by two before you reach 1. Consequently, the total work is O(n2 log n).
最后，当外循环运行时，它每次迭代都会执行O（n2）工作。它也运行O（log n）次迭代，因为它的运行时间等于在达到1之前必须将n除以2的次数。因此，总工作量为O（n2 log n）。
In general, you cannot just multiply loops together, since their bounds might depend on one another. In this case, though, since there is no dependency, the runtimes can just be multiplied. Hopefully the above reasoning sheds some light on why this is - it's because if you work from the inside out thinking about how much work each loop does and how many times it does it, the runtimes end up getting multiplied together.
通常，您不能将循环相乘，因为它们的边界可能相互依赖。但是，在这种情况下，由于没有依赖性，运行时可以成倍增加。希望上面的推理能够解释为什么会这样 - 这是因为如果你从内到外思考每个循环做了多少工作以及它做了多少次，那么运行时最终会成倍增加。
Hope this helps!
希望这可以帮助！
#2
2
- Yes, this is correct: the outer loop is
logN, the other two areNeach, for the total ofO(N^2*LogN) - 是的，这是正确的：外部循环是logN，另外两个是N，每个都是O（N ^ 2 * LogN）
- In the simple cases, yes. In more complex cases, when loop indexes start at numbers indicated by other indexes, the calculations are more complex.
- 在简单的情况下，是的。在更复杂的情况下，当循环索引从其他索引指示的数字开始时，计算更复杂。
#3
2
To answer this slightly (note: slightly) more formally, say T(n) is the time (or number of operations) required to complete the algorithm. Then, for the outer loop, T(n) = log n*T2(n), where T2(n) is the number of operations inside the loop (ignoring any constants). Similarly, T2(n) = n*T3(n) = n*n.
为了更正式地回答这个问题（注意：稍微），说T（n）是完成算法所需的时间（或操作次数）。然后，对于外循环，T（n）= log n * T2（n），其中T2（n）是循环内的操作数（忽略任何常数）。类似地，T2（n）= n * T3（n）= n * n。
Then, use the following theorem:
然后，使用以下定理：
If f1(n) = O(g1(n)) and f2(n) = O(g2(n)), then f1(n)×f2(n) = O(g1(n)×g2(n))
(source and proof)如果f1（n）= O（g1（n））且f2（n）= O（g2（n）），则f1（n）×f2（n）= O（g1（n）×g2（n）） （来源和证明）
This leaves us with T(n) = O(n2logn).
这使我们得到T（n）= O（n2logn）。
"Combining nested loops" is just an application of this theorem. The trouble can be in figuring out exactly how many operations each loop uses, which in this case is simple.
“组合嵌套循环”只是该定理的一个应用。问题在于确定每个循环使用的确切操作数量，在这种情况下很简单。
#4
0
You can proceed formally using Sigma Notation, to faithfully imitate your loops:
您可以正式使用Sigma Notation，忠实地模仿您的循环：