Python程序计算给定数组中大小为三的反向对数

反向对数是一种步骤计数方法，通过它我们可以计算特定数组所采取的排序步骤数。它也能够计算数组的操作时间跨度。但是，如果我们想以反向方式对数组进行排序，计数将是该数组中存在的最大数字。

Array: { 5, 4, 3, 2, 1}  // for the reverse manner
Pairs: {5, 4}, {5,3} , {3,2}, {3,1}, {2,1},{4,3}, {4,2}, {4,1},}, {5,2}, {5,1}
Output: 10
Array: {1, 2, 3, 4, 5}  // for the increasing manner
Pairs: No Pairs
Output: 0
Array: {1,5,2,8,3,4}
Pairs: {5, 2}, {5, 3}, {5, 4}, {8, 3}, {8, 4}
Output: 5

反向对数指示特定数组距离按递增顺序排序有多远。以下是两个特定过程来描述这种情况，并附带解决方法。

查找较小的元素：要从数组中查找较小的元素，我们需要从n-1到0迭代索引。通过应用(a[i]-1)，我们可以在此处计算getSum()。该过程将一直运行，直到它到达a[i]-1。
查找更大的数字：要从索引中查找更大的数字，我们需要执行0到n-1的迭代。对于每个元素，我们需要为每个数字做计算，直到a[i]。从i中减去它。然后我们将得到一个大于a[i]的数字。

在数组中计算大小为三的反向对数的算法

在此算法中，我们学习如何在特定的编程环境中计算给定数组中大小为三的反向对数。

步骤1 – 开始
步骤2 – 声明一个数组和反向计数(As arr[] -> 数组和invCount -> 反向计数)
步骤3 – 内循环y=x+1到N
步骤4 – 如果元素x大于y索引处的元素
步骤5 – 然后，增加invCount++
步骤6 – 打印对
步骤7 – 终止

计算数组中大小为三的反向对数的语法：

def getInversions(A, n):
count = 0
for i in range(n):
for j in range(i + 1, n):
if A[i] > A[j]:
   count += 1
return count;

这里我们已经提到了计算给定数组中大小为三的反向对数的可能语法。对于此方法，时间复杂度为O(N^2)，其中N为数组的总大小；空间复杂度：O(1)，因为没有额外的空间被使用。

要遵循的方法

方法1 – 通过大小为3的计数反向对程序计算给定数组中的反向对数
方法2 – 更好的计算大小为3的反向对数的方法
方法3 – 使用二进制索引树计算大小为3的反向对数

通过大小为3的计数反向对程序计算给定数组中的反向对数

为了计算大小为3的反向对数的简单方法，我们需要针对i，j和k的所有可能值运行循环。时间复杂度为O(n^3)，而O(1)反映了辅助空间。

条件是 –

a[i] & gt; a[j] > a[k]并且i < j < k。

示例1

def getInvCount(arr):
   n = len(arr)
   invcount = 0
   for i in range(0,n-1):
      for j in range(i+1 , n):
         if arr[i] > arr[j]:
            for k in range(j+1 , n):
               if arr[j] > arr[k]:
                  invcount += 1
   return invcount
arr = [7 , 16, 2 , 1]
print ("执行操作后反转计数:%d" %(getInvCount(arr)))

输出

执行操作后反转计数：2

更好的方法来计算大小为3的反转

在此方法中，我们将数组的每个元素都视为反转的中间元素。这有助于降低复杂度。对于此方法，时间复杂度为O（n ^ 2），辅助空间为O（1）。

示例2

def getInvCount(arr, n):
    invcount = 0
    for i in range(1,n-1):
        small = 0
        for j in range(i+1 ,n):
            if (arr[i] > arr[j]):
                small+=1
        great = 0;
        for j in range(i-1,-1,-1):
            if (arr[i] < arr[j]):
                great+=1
        invcount += great * small
    return invcount
arr = [8, 4, 2, 1]
n = len(arr)
print("在方法运行后的反转计数：",getInvCount(arr, n))

输出

在方法运行后的反转计数：4

使用二进制索引树计算大小为3的反转

在此方法中，我们计算较大的和较小的元素。然后执行乘操作 greater[] 和 smaller[]，并将其添加到最终结果中。因此，时间复杂度为O(n*log(n)) ，辅助空间为O(n)。

示例3

def getSum(BITree, index):
    sum = 0
    while (index > 0):
        sum += BITree[index]
        index -= index & (-index)

    return sum

def updateBIT(BITree, n, index, val):
    while (index <= n):
        BITree[index] += val
        index += index & (-index)

def getInvCount(arr, n):
    invcount = 0 
    maxElement = max(arr)
    BIT = [0] * (maxElement + 1)
    for i in range(n - 1, -1, -1):
        invcount += getSum(BIT, arr[i] - 1)
        updateBIT(BIT, maxElement, arr[i], 1)
    return invcount

if __name__ =="__main__":
    arr = [8, 4, 2, 1]
    n = 4
    print("执行操作后的反转计数: ", getInvCount(arr, n))