大O符号 - 发现复杂性

Question

我正在做一个测验 - 我做得很好，但以下片段。帮助我了解这将是哪种表示法？

我的选择是：O(n^2)，O(n^3)，O(nlogn)和O(n+n^2)

代码段是：

for (int i = 0; i < n; i++) { 
System.out.println("hello");
} 
for (int i = 0; i < n; i++) { 
for (int j = 0; j < i; j++) { // NOTE j < i here. 
System.out.println("hello");
}
} 

Answer 1

第一个循环很容易：身体正好跑了n次，所以它O(n).

第二个需要多思考一下。很明显，外循环运行n次，但内循环体多久执行一次？第一次通过外循环时，我们有i == 0，所以内循环体执行 0 次(即使对于j == 0j < i也是假的)。第二次，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.在大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)。

Answer 2

(这就是我的想法，我不能发表评论，因为我没有足够的声誉，但我想把它扔掉)

第一个循环是线性的，因此具有刚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)。