java - 算法的运行时间

Question

我不明白为什么下面的算法的运行时间是O(nlogn)。有人可以帮我吗？

public static boolean unique2(int[] data) {
  int n= data.length;
  int[] temp= Arrays.copyOf(data,n);
  Arrays.sort(temp);
  for (int j=0; j<n-1;j++)
    if (temp[j]==temp[j+1])
      return false;
  return true;
}

Answer 1

Arrays.sort(temp) 需要 O(nlogn)，因为这是最有效的排序算法的运行时间，并且 JDK 实现使用 O(nlogn) 算法。

该方法的其他部分 - Arrays.copyOf(data,n) 和循环需要 O(n) 时间，因为它们迭代数组一时间。

因此总体运行时间为O(nlogn)。