0

我想知道我的算法在这种方法中的确切时间复杂度。我认为它是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)
    }
4

3 回答 3

2

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

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

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

但是，在数组或集合中找到最大的元素总是 O(n)，因为我们可以简单地遍历每个元素并跟踪最大值。

于 2013-11-06T01:17:46.220 回答
1

实际上，它是 O(nlogn)。Arrays.sort() 使用归并排序。但是，使用此方法可能不是找到最大值的最佳方法。您可以只循环遍历数组，而是比较元素。

于 2013-11-06T01:13:32.230 回答
1

“你只和你最慢的跑者一样快”——事实

因此，这里重要的运行时操作是您的排序和遍历数组。由于 Arrays.sort(num) 是一种最有效地对数组进行排序的方法，我们可以保证这将是 O(nlg(n))（其中 lg(n) 是 n 的以 2 为底的对数）。之所以如此，是因为 O 表示法表示最坏情况的运行时间。此外，阵列的步进需要 O(n)。

所以，我们有 O(nlgn) + O(n) + O(1) + ...

这实际上减少到 O(2nlg(n))。但是系数在渐近符号中可以忽略不计。因此，如上所述，您的运行时接近 O(nlg(n))。

于 2013-11-06T01:32:52.593 回答