基于分治法的数组逆序对计数算法：基本操作识别与递推关系构建方法问询

1. 确定算法的基本操作 #

先看你提供的代码，整个算法的核心耗时操作集中在merge函数的最内层while循环里：

while (i <= mid && j <= high) {
    if (arr[i] <= arr[j]) { // 这是核心的基本操作
        // ...
    } else {
        // ...
    }
}

这里的数组元素比较操作（arr[i] <= arr[j]）就是我们要找的基本操作。原因很简单：它是算法中执行次数最多的操作，每次循环迭代都会触发一次，且是决定合并逻辑走向的关键步骤，对总运行时间的贡献最大。

2. 建立递推关系分析基本操作次数 #

我们用T(n)表示处理一个长度为n的数组时，基本操作（比较）的总执行次数，接下来分基准情况和递归情况推导递推式：

基准情况 #

当数组长度n=1时（对应mergeSort里的high == low的情况），没有元素需要比较，所以：
T(1) = 0

递归情况 #

当n > 1时，分治算法会做三件事：

• 分解：把数组拆分成两个长度为n/2的子数组，这一步只是计算中点mid，不涉及任何比较操作，所以没有额外代价。
• 递归求解：分别递归处理两个子数组，这部分的基本操作次数是2 * T(n/2)。
• 合并：合并两个已排序的子数组时，基本操作的次数是多少？
  合并阶段的while循环会持续比较左右子数组的当前元素，直到其中一个子数组的元素被全部处理完。对于总长度为n的两个子数组，最多需要n-1次比较（比如左半部分所有元素都比右半部分大的最坏情况），最少需要⌈n/2⌉次比较（比如其中一个子数组的元素全部小于另一个的最好情况），但从渐近分析的角度，合并阶段的比较次数是线性的，我们可以用C(n) = n - 1来表示精确的代价，或者用Θ(n)表示渐近复杂度。

综上，递归情况下的递推式为：
T(n) = 2*T(n/2) + (n - 1)

递推式的求解 #

我们可以用递归树法来解这个递推式：

• 每一层的总代价都是n-1（或者近似为n），递归树的深度是log₂n。
• 把所有层的代价加起来：总代价 = (n-1) * log₂n，渐近上等价于Θ(n log n)。

这也符合归并排序的时间复杂度特性——因为这个逆序对算法本质是在归并排序的基础上增加了逆序计数的逻辑，核心的比较操作次数和归并排序是一致的。

内容的提问来源于stack exchange，提问作者Rocket