该题要求时间复杂度问题

Question

for(i = n-1; i > 1; i--)
  for(j = 1; j < i; j++)
    if(A[j] > A[j+1])
      A[j]与A[j+1]交换;

求此算法的时间复杂度

Answer 1

是O(n的平方)
实际运行次数为：
n-1 + n-2 + n-3 + ... + 3 + 2 + 1 = (n-1) * (n-1 + 1) / 2 = n * (n-1) / 2 = 0.5 * n * n - 0.5 * n ，所以是O(n的平方)