for i = 0 to size(arr)
for o = i + 1 to size(arr)
do stuff here
什么是这样做的最坏时间复杂度？ 这不是N ^ 2，由于第二逐个每i循环降低。 这不是N，它应该更大。 N-1 + N-2 + N-3 + ... + N-N + 1。
Answer 1:
它是 N ^ 2 ，因为它是两个线性复杂性的乘积。
（还有一个原因渐进复杂被称为渐进和不相同 ......）
参见维基百科上进行了简化的解释 。
Answer 2:
你可以把它像你与anxn矩阵工作。 你大致工作在矩阵中的元素的一半，但为O（n ^ 2/2）是相同的为O（n ^ 2）。
Answer 3:
当你要确定复杂类的算法中，所有你需要的是找到在算法的复杂功能中增长最快的任期。 例如，如果您有复杂函数f(n)=n^2-10000*n+400 ，找到O(f(n))你只需要找到在功能上“最强”一词。 为什么？ 因为n足够大，只有这个词决定了整个函数的行为。 话虽如此，很容易看到，无论f1(n)=n^2-n-4和f2(n)=n^2是在O(n^2) 然而，他们，对于相同的输入大小n ，没有为相同的时间内运行。
在你的算法，如果n=size(arr)在do stuff here代码将运行f(n)=n+(n-1)+(n-2)+...+2+1次。 这是很容易看到， f(n)表示的算术级数的总和，这意味着f(n)=n*(n+1)/2 ，即， f(n)=0.5*n^2+0.5*n 。 如果我们假设do stuff here是O(1)那么你的算法O(n^2)的复杂性。
对于i = 0至大小（ARR）
我假定当循环结束i变得大于size(arr)不等于。 然而，如果是后者的情况下，除f(n)=0.5*n^2-0.5*n ，它仍然是在O(n^2) 请记住， O(1),O(n),0(n^2) ，...是复杂的类，和算法复杂性的功能是描述，对于输入大小n的功能，多少步有在算法。
Answer 4:
这是n*(n-1)/2 ，它等于O(n^2)
文章来源: What's the complexity of for i: for o = i+1
