爲什麼我的O（NLogN）算法找到字符比我的O（N）算法運行得更快？

Question

我有一個長度相同的單詞的哈希集。我想查找存在於這個哈希集合中的所有字形，並將它們收集到另一個稱爲anagrams的哈希集合中。這裏是做環路：

public HashSet<String> getUniqueAnagramsSlow(HashSet<String> paddedWords, int areAnagramsVersion){ 
    HashSet<String> anagrams = new HashSet<String>(); 
    Object[] paddedWordsArr = paddedWords.toArray(); 
    for(int i = 0; i < paddedWordsArr.length-1; i++){ 
     boolean foundAnagram = false; 
     String wordOne = (String) paddedWordsArr[i]; 
     if(!anagrams.contains(wordOne)) 
      for(int j = i+1; j < paddedWordsArr.length; j++){ 
       String wordTwo = (String) paddedWordsArr[j]; 
       if(areAnagrams(wordOne, wordTwo, areAnagramsVersion)){ 
        foundAnagram = true; 
        anagrams.add(wordTwo); 
       } 
      } 
     if(foundAnagram){ 
      anagrams.add(wordOne); 
     } 
    } 
    return anagrams; 
} 

我寫這段代碼的目標是看到不同areAnagram（）函數可以如何影響運行時間。我寫了兩個版本的areAnagrams（）。將兩個字符串排序並將它們與另一個使用hashmaps比較字符頻率的字符串進行比較。在這裏，他們是：

public boolean areAnagramsVersionOne(String first, String second){ 
    char[] arr1 = first.toCharArray(); 
    Arrays.sort(arr1); 
    String fSorted = new String(arr1); 
    char[] arr2 = second.toCharArray(); 
    Arrays.sort(arr2); 
    String sSorted = new String(arr2); 
    return fSorted.equals(sSorted); 
} 
public boolean areAnagramsVersionTwo(String first, String second){ 
    HashMap<String, Integer> wordOne = new HashMap<String,Integer>(); 
    for(int i = 0; i < first.length(); i++){ 
     String letOne = first.substring(i, i+1); 
     if(wordOne.containsKey(letOne)){ 
      int letOneFreq = wordOne.get(letOne); 
      wordOne.put(letOne, letOneFreq + 1); 
     }else{ 
      wordOne.put(letOne, 1); 
     } 
    } 
    for(int i = 0; i < second.length(); i++){ 
     String letTwo = second.substring(i, i+1); 
     if(!wordOne.containsKey(letTwo)) 
      return false; 
     int freq = wordOne.get(letTwo); 
     if(freq == 0) 
      return false; 
     wordOne.put(letTwo, freq-1); 
    } 
    return true; 
} 

從我的理解，areAnagramsVersionOne（）將在NlogN時間和areAnagramsVersionTwo（運行），將在n時間運行。但是，當我在原始循環中測試這兩個版本的anagrams時，版本2明顯較慢。爲什麼是這樣？

謝謝。

這是如何我測試跑時間的示例：

long startTime = System.currentTimeMillis(); 
getUniqueAnagramsSlow(words, 2); 
long endTime = System.currentTimeMillis(); 
System.out.println("exec time: " + (endTime - startTime)); 

Answer 1

據我知道O（NlogN）保證是比O（N）僅大對於N足夠大的值，因爲在小值時，不用O（）表示法表示的係數和常數仍然相關。考慮2種算法，使得它們的成本爲：

算法1成本：100 * N：O（N）

算法2成本：10 * NlogN：O（NlogN）

O（NlogN）> O（N）=> 10 * NlogN> 100 * N => 10 * logN> 100 => logN> 10

因此在這種情況下，當N> 2^10時，算法2的成本會高於算法1。對於較小的值，算法2的成本較低，即使根據O（）表示法「效率較低」。

閱讀the wikipedia page for O() notation瞭解更多詳情。