Java 使用 Big O(n log n) 或 Big O(log n) 复杂度的程序

Question

我正在尝试创建一个 Java 程序来查找 2 个数组之间的公共 elements/ages。但是，我需要算法必须在 Big O(n log n) 或 Big O(log n) 时间复杂度上达到运行。这是我想出的，关于如何改进它的任何想法？我也算对了操作步骤吗？

int [] AgeMale = {21, 19, 24, 22, 20, 23, 18};  //Program is executed 1 time
int [] AgeFemale = {17, 17, 22, 19};            //Program is executed 1 time
System.out.println("Age of male students: " + Arrays.toString(AgeMale)); //Title. Program is executed 1 time
System.out.println("Age of female students: " + Arrays.toString(AgeFemale)); //Title. Program is executed 1 time
    
for (int x = 0; x < AgeMale.length; x++) //Loop is executed n times, therefore, O(n).
{
    for (int y = 0; y < AgeFemale.length; y++) //Loop is executed n times, therefore O(n).
    {
        if (AgeMale[x] == AgeFemale[y])     // Executed n * n time 
        {
                System.out.println("The common ages are: " + AgeMale[x]); // Program is executed 1 time.
        }
    }
}

Answer 1

您当前的算法具有 O(mn) 的复杂度，其中 m 是数组中元素的数量 AgeMale 并且 n 是数组中元素数量的开始数组 AgeFemale.

为了改进您的算法，您可以将其中一个数组转换为 set (e.g., an HashSet). From source 一个可以阅读的数组：

Time Complexity of HashSet Operations: The underlying data structure for HashSet is hashtable. So amortize (average or usual case) time complexity for add, remove and look-up (contains method) operation of HashSet takes O(1) time.

可以选择两个数组中最小的一个转化为集合。从数组转换为set 的时间复杂度为S，其中S 是最小数组的大小。换句话说，来自 HashSet 的方法 add 将被调用 S 次。

然后检查最大数组的元素是否存在于那个集合。这将具有 L 的时间复杂度，其中 L 是最大数组的大小。

总的来说，上述算法的时间复杂度为O(S + L).

一个运行例子：

public static void main(String[] args) {
    int [] ageMale = {21, 19, 24, 22, 20, 23, 18};  //Program is executed 1 time
    int [] ageFemale = {17, 17, 22, 19};            //Program is executed 1 time
    System.out.println("Age of male students: " + Arrays.toString(ageMale));
    System.out.println("Age of female students: " + Arrays.toString(ageFemale));
    Set<Integer> female_ages = new HashSet<>(ageFemale.length);
    for (int age : ageFemale) // Time complexity of O(S)
        female_ages.add(age); // Time complexity of O(1)

    for (int age : ageMale) { // Time complexity of O(L)
        if(!female_ages.add(age)){ // Time complexity of O(1)
            System.out.println("The common ages are: " + age);
        }
    }
}

输出：

Age of male students: [21, 19, 24, 22, 20, 23, 18]
Age of female students: [17, 17, 22, 19]
The common ages are: 19
The common ages are: 22

Java 使用 Big O(n log n) 或 Big O(log n) 复杂度的程序

Java Program using Big O(n log n) or Big O(log n) complexity

java

performance

big-o

time-complexity