python - 该方法查找数组(python)中的反转次数的时间复杂度是多少？

Question

inv=0
for j in range(n):
     inv=inv+ sum((x<arr[j]) for x in arr[j:] )

对于每个元素，我都会检查数组中小于该元素之后出现的元素数量。(arr[j : ])

Answer 1

它是O(n²)。以下是计算方法:

• 对于第 1^st 个元素，您需要与接下来的 n-1 个元素进行比较。

• 对于第 2^nd 个元素，您需要与接下来的 n-2 个元素进行比较。

  ...

• 对于第 n 个元素，您需要与接下来的 0 个元素进行比较。

因此，您总共进行 (n-1) + (n-2) + ... + 1 + 0 = n(n-1)/2 次比较，这是 n 的二次方。

<小时/>

确实存在更有效的方法。例如，通过使用基于分而治之的策略，您可以O(n log(n))来计算它们。请参阅this nice link !