性能使用Arrays.sort

-1

我有，在以下的方式使用Arrays.sort(char[])一個代碼陣列分析的：性能使用Arrays.sort

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 * n日誌（N）*（N * n日誌（n））的還是我的路要走

感謝

編輯：？？我要補充的是，雖然n與數組大小有關，Arrays.sort正在處理數組元素中的字母數目，這是我的混淆的一部分，如果這應該被添加到性能分析中

Edit2：低調選民留下評論，爲什麼它被認爲是一個不好的問題。

來源

2012-01-31 arin

你的琴絃有多久了？這就是你的Arrays.sort大O中的'n'，它與數組大小中的'n'不一樣。如果你有最大的字符串長度，Arrays.sort位被一個常量限制。 – 2012-01-31 22:11:06

字符串大小沒有限制。 – arin 2012-01-31 22:23:08

然後你的複雜度估計將不僅取決於'n'，還取決於字符串的大小。下面的答案很好。 – 2012-01-31 22:27:36

如果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]，然後在in你爲排序array[1]到array[n]。

然後當a爲1時，您首先將array[1]分類，然後在內部for循環array[2]到array[n]。 但是你已經整理了所有的，而且它並不像在此期間它會發生變化。

來源

2012-01-31 22:14:41

我想你忽略了'陣列。在外部循環內進行排序（char []）'調用。然而，你所說的話很有道理。這是一種提高性能的方法。 – arin 2012-01-31 22:25:09

對數組排序一次。那就是'O（n（m log m））'。然後比較數組就是一個嵌套循環，那就是'O（n^2 m）'，因爲最壞的情況是，你必須比較每個中的'm'個字符。 – 2012-01-31 22:32:57

對，完全忽略了比較。 – 2012-01-31 22:38:04

在運行Ñ外循環，其中的每一個運行Ñ內部循環，其中的每一個調用一個O（Ñ日誌Ñ）算法，因此最終結果 - 不存在的電平之間的任何相互作用 - 爲O （n log n）。

來源

2012-01-31 22:09:23

在外循環中還有一個O（n log n）算法調用。 – arin 2012-01-31 22:13:01

性能使用Arrays.sort

回答

相關問題