3个嵌套循环的大O.
另一个大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++; } } } 我的想法：所以打破它，我认为外部循环是O(log2(n)) ，然后每个内部循环是O(n) ，这将导致O(n^2 * log2(n))问题＃ 1是正确的吗？
问题2：当组合嵌套循环时，它总是像每个循环的大O一样简单吗？
当循环计数器不相互依赖时，它总是可以从内向外工作。
最内层循环总是花费时间O（n），因为无论j和i的值如何，它都会循环n次。
当第二个循环运行时，它运行O（n）次迭代，在每次迭代时执行O（n）工作以运行最内层循环。 这需要时间O（n 2 ）。
最后，当外循环运行时，它每次迭代执行O（n 2 ）次操作。 它也运行O（log n）次迭代，因为它的运行时间等于在达到1之前必须将n除以2的次数。因此，总工作量为O（n 2 log n）。
通常，您不能将循环相乘，因为它们的边界可能相互依赖。 但是，在这种情况下，由于没有依赖性，运行时可以成倍增加。 希望上面的推理能够解释为什么会这样 – 这是因为如果你从内到外思考每个循环做了多少工作以及它做了多少次，那么运行时最终会成倍增加。
希望这可以帮助！
- 是的，这是正确的：外部循环是
logN，另外两个是N每个都是O(N^2*LogN) - 在简单的情况下，是的。 在更复杂的情况下，当循环索引从其他索引指示的数字开始时，计算更复杂。
为了更正式地回答这个问题（注意：稍微），说T(n)是完成算法所需的时间（或操作次数）。 然后，对于外循环， T(n) = log n*T2(n) ，其中T2(n)是循环内的操作数（忽略任何常数）。 类似地，T2（n）= n * T3（n）= n * n。
然后，使用以下定理：
如果f 1 （n）= O（g 1 （n））且f 2 （n）= O（g 2 （n）），则f 1 （n）×f 2 （n）= O（g 1 （n） ）×g 2 （n））
（来源和certificate）
这使我们得到T（n）= O（n 2 logn）。
“组合嵌套循环”只是该定理的一个应用。 问题在于确定每个循环使用的确切操作数量，在这种情况下很简单。
您可以正式使用Sigma Notation，忠实地模仿您的循环：
