使用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正在处理数组元素中的字母数.如果应该将其添加到性能分析中,这是我困惑的一部分.

编辑2:如果下选民留下评论为什么它被认为是一个糟糕的问题,那将是很酷的.

Answer 1

如果n是数组的长度,并且m是array[i]每个n^2迭代的长度,那么你将在每次迭代时执行O(m log m)排序,所以总体而言O(n^2 (m log m))(或者O(n^3 log n)如果n == m.[编辑:现在我想更多关于这一点,你的猜测是对的,这是错误的复杂性.但我在下面说的仍然是正确的!]]

但这并不是必需的.您可以只生成数组的排序副本,然后使用该数组执行嵌套for循环.看的时候会发生什么a是0:首先你排序array[0],然后在内部进行循环您排序array[1]通过array[n].

然后,当a是1,你先排序array[1],然后在内部for循环array[2]通过array[n].但是你已经对所有这些进行了排序,并且它不会在过渡期间发生变化.