使用 Arrays.sort 进行数组分析的性能

Question

我有一个按以下方式使用 Arrays.sort(char[]) 的代码：

    void arrayAnalysis(String[] array){
      for(int a=0; a<array.length;a++){
        char[] letters = array[a].toCharArray();
        Arrays.sort(letters);
        ...
        for(int b=a+1; b<array.length;b++){
          char[] letters2 = array[b].toCharArray();
          Arrays.sort(letters2);

          if(Arrays.equals(letters, letters2)
            print("equal");
        }
      }
    }

在本例中，n 等于数组大小。由于嵌套的 for 循环，性能自动为 O(n^2)。但是，我认为 Arrays.sort （使用 O(nlog(n))）也会影响性能并使其比 O(n^2) 更糟糕。这种想法正确吗？

最终的性能会是 O(n*nlog(n)*(n*nlog(n)) 吗？还是我离题太远了？

谢谢。

编辑：我应该补充一点，虽然 n 与数组大小有关，但 Arrays.sort 是如果应该将其添加到性能分析中，这是我感到困惑的一部分。

Edit2：如果反对者留下评论来说明为什么它被认为是不好的，那就太酷了。问题。

Answer 1

如果 n 是数组的长度，m 是每个 array[i] 的长度，那么您将在每个 < code>n^2 次迭代，执行 O(m log m) 排序，因此总体来说是 O(n^2 (m log m)) (或 O(n^3 log n) 如果 n == m. [编辑：现在我想得更多了，你的猜测是正确的，这是错误的复杂性，但我下面所说的仍然是正确的！]]

但这并不是真正必要的。您可以创建数组的排序副本，然后使用该副本执行嵌套 for 循环，看看当 a 为 0 时会发生什么：首先对 array[0]，然后在内部 for 循环中进行排序array[1] 到 array[n]

然后，当 a 为 1 时，首先对 array[1] 进行排序。 >，然后在内部 for 循环 array[2] 到 array[n] 中。但你已经对所有这些进行了排序，并且它不是这样的。是否在此期间发生了变化。

Answer 2

您运行 n 个外循环，每个循环运行 n 个内循环，每个循环调用 O(n log n）算法，因此最终结果（级别之间没有任何交互）为 O(n³ log n)。