int cnt = 0;
for (int i = 1; i < n; i++) {
for (int j = i; j < n; j++) {
for (int k = j * j; k < n; k++) {
++cnt;
}
}
}
我不知道。如何分析它的时间复杂性？
很容易看出代码是Omega(n²((也就是说，是最小二次方(-两个外循环执行大约n²/2次。
内部k循环执行零次，除非j小于sqrt(n)。即使它执行零次，也需要一些计算来计算循环的条件，所以在这些情况下它是O(1(工作的。
当j小于sqrt(n)时，i也必须小于sqrt(n)，因为通过构造循环，j总是大于或等于i。在这些情况下，k循环进行n-j²迭代。在这些情况下，我们可以为这个内循环中的总功量构造一个界：i和j都小于sqrt(n(，并且在最坏的情况下，在k循环中完成了O(n(功，所以在内循环中最多完成了O。
对于内环是琐碎的情况(即：当j>sqrt(n(时(，最多也有O(n²(的总功。
这证明了代码的运行时复杂度为θ(n²(。
涉及单独查看嵌套循环并为其构建big-O边界的方法通常不会给出紧边界，这是一个这样的方法失败的示例问题。
第一种方法是分别查看循环，这意味着我们有三个O(.(通过乘积连接。因此，
算法的复杂度=O(OuterLoop(*O(MiddleLoop(*O(InnerLoop(
现在分别来看每个循环：
Outerloop：这是最简单的一个。从1增加到n，导致O(n(
Middleloop：这是不明显的，循环的终止条件仍然是n，但起始迭代器值是i，这意味着i越大，完成循环所需的时间就越短。但这个因子是二次方的，渐近地只是一个常数，这意味着它仍然是O(n(，因此O(n^2("；直到"；第二个循环。
内部循环：我们看到，迭代器按二次方递增。但我们也看到，二次增长取决于第二个环路，我们说它是O(n(。由于，我们再次只无症状地看待复杂性，这意味着我们可以假设j线性上升，并且由于k二次上升直到n，因此需要\平方(n(次迭代，直到达到n。这意味着最内部的循环的运行时间为O(\square(n((。
把所有这些结果放在一起，
O(n*n*平方(n((=O(n^2*平方(n((