如何将代码时间复杂度从O(n log m + m log m)优化为O(n log n + m log n)

要满足目标时间复杂度，只需调换原代码中排序与查找的集合对象，具体逻辑如下：

• 原代码排序长度为m的set1，再对set2的n个元素做二分查找，总复杂度为O(m log m + n log m)
• 改为排序长度为n的set2，再对set1的m个元素做二分查找：排序时间为O(n log n)，m次二分查找时间为O(m log n)，总复杂度正好是O(n log n + m log n)

修改后的Java代码：

import java.util.Arrays;

public class Main {

    // Returns true if set1[] and set2[] are disjoint, else false
    static boolean areDisjoint(int[] set1, int[] set2, int m, int n) {
        // 改为排序set2数组，对应时间复杂度O(n log n)
        Arrays.sort(set2);

        // 遍历set1的每个元素，在排序后的set2中做二分查找（每次O(log n)）
        for (int i = 0; i < m; i++) {
            int lb = Arrays.binarySearch(set2, set1[i]);
            // 若元素存在则返回false
            if (lb >= 0)
                return false;
        }

        // 无交集则返回true
        return true;
    }

    // Driver program to test the above function
    public static void main(String[] args) {
        int[] set1 = {12, 34, 11, 9, 3};
        int[] set2 = {7, 2, 1, 5};
        int m = set1.length;
        int n = set2.length;
        System.out.println(areDisjoint(set1, set2, m, n) ? "Yes" : "No");
    }
}

补充说明 #

• Java中Arrays.sort()针对基本类型数组采用双枢轴快速排序，时间复杂度稳定在O(k log k)（k为数组长度），完全符合需求
• Arrays.binarySearch()的时间复杂度为O(log k)，此处k为排序后的set2长度n

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