时间戳

首页 > 解决方案 > 使用 Big O(n log n) 或 Big O(log n) 复杂度的 Java 程序

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

问题描述

我正在尝试创建一个 Java 程序来查找 2 个数组之间的公共元素/年龄。但是，我需要算法必须在大 O(n log n) 或大 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.
        }
    }
}

标签： javaperformancetime-complexitybig-o

解决方案

您当前的算法的复杂度为O(mn),m是数组中元素的数量，并且是数组AgeMale中n元素的数量AgeFemale。

为了改进您的算法，您可以将其中一个数组转换为一个集合（例如，一个HashSet）。从源代码可以阅读：

HashSet 操作的时间复杂度：HashSet 的底层数据结构是 hashtable。因此，HashSet 的添加、删除和查找（包含方法）操作的摊销（平均或通常情况）时间复杂度需要 O(1) 时间。

您可以选择两个数组中最小的一个来转换为set。从数组转换为集合的时间复杂度为S，其中S是最小数组的大小。换句话说，方法 add from theHashSet将被调用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

推荐阅读