java - 我的程序的时间复杂度

Question

我想知道我的算法在此方法中的确切时间复杂度。我认为它是 nlogn，因为它使用 arrays.sort;

public static int largestElement(int[] num) throws NullPointerException // O(1)
    {
    int a=num.length; // O(1)
    Arrays.sort(num); // O(1)? yes

    if(num.length<1) // O(1)
    return (Integer) null;
    else
    return num[a-1]; // O(1)
    }

Answer 1

您在帖子中似乎严重自相矛盾。你是正确的，因为该方法是 O(nlogn)，但以下是不正确的:

Arrays.sort(num); // O(1)? yes

如果你是对的，该方法的复杂度将是 O(1)!毕竟，一堆 O(1) 的进程按顺序仍然是 O(1)。实际上，Arrays.sort() 的复杂度为 O(nlogn)，它决定了方法的整体复杂性。

但是，在数组或集合中查找最大元素始终可以是 O(n)，因为我们可以简单地迭代每个元素并跟踪最大值。