第一个循环很简单：身体准确地运行 n 好几次了，所以 O(n) .
第二个需要更多的思考。很明显，外环在运行 n 但是内部循环体多久执行一次？第一次通过外环，我们有 i == 0 ，因此内部循环体执行0次( j < i 是假的 j == 0 ). 第二次， i == 1 所以内环体执行1次。一般来说，它是被执行的 i 时间，例如 i = 0, ..., n-1 .
所以内环体的执行总数，我们称之为 S ，是 S = 0 + 1 + ... + n-1 . 现在有一个很好的技巧，可以把它变成一个封闭形式的方程。写一次，然后再反过来写一次：

S =  0  +  1  + ... + n-2 + n-1
 S = n-1 + n-2 + ... +  1  +  0

然后将两个方程相加：

S  =  0  +  1  + ... + n-2 + n-1
 S  = n-1 + n-2 + ... +  1  +  0
------------------------------- +
2*S = n-1 + n-1 + ... + n-1 + n-1

所以呢 2*S 等于 n 次 n-1 . 由此，我们很容易发现 S = n * (n-1) / 2 . 这可以重写为 S = ½*n^2 - ½*n . 在big-o形式中，只有最高阶项存在，常量存在 ½ 没关系，所以这是 O(n^2) .
得到相同结果的更“手工”的方法是：平均来说，内部循环运行， n/2 次（给或拿一次），外部循环运行 n 一次又一次的给予 O(½*n*n) = O(n^2) .
结合 O(n) 第一个循环，与 O(n^2) ，预期的答案可能是 O(n^2) .
但请注意技术上 O(n+n^2) 也是正确的，因为 O(n + n^2) = O(n^2) . 同样，低阶项 n 无所谓渐近。甚至 O(n^3) 技术上是正确的，因为 n^3 支配 n^2 ; 然而，复杂性既不是 Ω(n^3) 也不是 θ(n^3) .

（这是我的想法，我不能评论，因为我没有足够的声誉，但我想扔掉这个）
第一个循环是线性的，因此具有 O(N) .
但是，对于第二/第三个循环，第二个循环是 N 次。内部循环将运行 N/2 时间是因为 j 总是小于 i ，（从不相等）。因此，这些循环的复杂性是 N(N/2) ，或 N^2/2 . 因为大o是一个常数， N/2 以及 N - 1 是同时的，所以我们也可以说是 N(N-1) ，或 N^2 - N .
如果我们把这两种复杂性加在一起，我们就有了 (N) + (N^2 - N) ，我们得到 N^2 . 因此，最终的结果是 O(N^2) .