最好情况和最坏情况的时间复杂度

Question

给定数组 A 的以下伪代码

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) 还是 Theta(n^2)，为什么？我好像不太明白这两者的区别

至于最好情况的复杂度，它与最坏情况的复杂度不一样，因为算法仍然要运行通过相同的线路吗？

Answer 1

该算法中的主导操作是比较A[i] > A[j]。此比较总是进行 n^2 次。

O(n^2) 表示这是最坏情况下的复杂度。如果你使用 O 表示法，你会说这种复杂性在最好的情况下可能会更好。

Theta(n^2) 表示这是所有情况下的复杂度。

所以答案是：复杂度是 Theta(n^2) 因为在最好和最坏的情况下都是 n^2。

Best case and worst case time complexity