最佳情况和最坏情况下的时间复杂度

x = 0 
    for i = 0 to n - 2 
    for j = i to n - 1 
     if A[i] > A[j]: 
      x = x + 1 
    return x

是对最坏情况的复杂性为O（n^2）或θ（N^2），为什么呢？我似乎不了解两者的区别。

至于最好的情况下的复杂性，它是不是最坏的情况下相同的复杂性，因为算法仍然必须通过相同的线路？

2016-10-01 Labbiqa

该算法中的主导操作是比较A[i] > A[j]。这个比较是总是完成n^2次。 O（n^2）表示这是最坏情况下的复杂度。如果你使用O符号，你会说这种复杂性在最好的情况下可能会更好。

Theta（n^2）表示这是全部个案的复杂程度。

所以答案是：复杂性是Theta（n^2），因为在最好的和最坏的情况下它都是n^2。

2016-10-01 11:56:23 Adam

感谢您的帮助！ – Labbiqa

比较**总是**执行（n-1）*（n + 2）/ 2次，当然是θ（n^2） –

回答