统计逆序对的Java代码时间复杂度是多少？是否满足O(n log n)要求

现有代码的复杂度结论 #

你写的这段逆序对统计代码时间复杂度确实是O(n²)，处理大数组时一定会出现运行变慢的问题，不符合*O(n log n)*的要求，原因如下：

• 这段代码本质是双重循环的变形写法：外层变量i从0遍历到数组长度减1，每轮i迭代时，j都会从1遍历到数组末尾，单轮i对应n次操作，总操作数是n*n量级，忽略常数项后复杂度就是O(n²)
• 当数组长度达到10000时，运算量就会达到1亿次，普通设备运行会出现明显卡顿，完全达不到*O(n log n)*的性能标准。

代码功能验证 #

你的代码逻辑是正确的，测试用例arr = {7, 3, 8, 1, 5}运行输出结果和预期的6一致，代码和运行结果如下：

public class Test {
    public static void main(String[] args) {
        int[] arr = {7, 3, 8, 1, 5};
        System.out.println();
        System.out.println("The number of pairs is " + countPair(arr));
    }
    public static int countPair(int[] arr) {
        int i = 0, j = 1;
        int ctr = 0;
        int len = arr.length;
        while (i < len) {
            if (j == len) {
                i++;
                j = 1;
            }
            else if (i < j && (arr[i] > arr[j])) {
                ctr++; // Counting pairs
            }
            j++;
        }
        return ctr;
    }
}

运行输出：

The number of pairs is 6

O(n log n)实现方案参考 #

要实现O(n log n)的逆序对统计，可以基于归并排序逻辑改造：归并排序拆分后的左右子数组都是有序的，合并过程中如果左数组当前元素大于右数组当前元素，那么左数组剩余的所有元素都可以和右数组当前元素组成逆序对，不需要逐个遍历统计，整体时间复杂度和归并排序一致为O(n log n)。

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