以下代碼的時間複雜度是多少？

Question

/* 
* Program to group anagrams from the string array input 
*/ 

import java.util.*; 

public class StringArrayAnagrams { 

    //function to group the anagrams together 
    public static void groupAnagrams(String[] inputArray) { 
     Hashtable<String, ArrayList<String>> store = new Hashtable<String, ArrayList<String>>(); //to store the sorted string as keys and words from input array that have same sort string 
     if (inputArray.length == 0) { 
      System.out.println("Input array is empty"); 
      return; 
     } else if(inputArray.length == 1) { 
      System.out.println(inputArray[0]); 
      return; 
     } 

     for(String word:inputArray) { 
      char[] temp = word.toCharArray(); 
      Arrays.sort(temp); 
      String tempStr = new String(temp); 
      if (store.containsKey(tempStr)) { 
       ArrayList<String> lStore = store.get(tempStr); 
       lStore.add(word); 
      } else { 
       ArrayList<String> newLStore = new ArrayList<String>(); 
       newLStore.add(word); 
       store.put(tempStr, newLStore); 
      } 
     } 
     //to print the grouped anagrams 
     Set<String> keySet = store.keySet(); 
     for(String eachKey:keySet) { 
      ArrayList<String> anagramList = store.get(eachKey); 
      System.out.println(anagramList); 
     } 
    } 

    public static void main(String[] args) { 
     String[] input = {"bat", "bta", "cat", "tca", "vish"}; 
     StringArrayAnagrams.groupAnagrams(input); 
    } 
} 

我寫了這段代碼，將字符串從輸入字符串數組中分組並打印出來。我仍然在努力學習如何回答代碼的時間複雜性。代碼的時間複雜度是多少？

Answer 1

該分類處理的是Java 8.

String[] input = {"bat", "bta", "cat", "tca", "vish"}; 
Collection<List<String>> grouped = Stream.of(input) 
      .collect(Collectors.groupBy(w -> sortLetters(w)) 
      .values(); 

public static String sortLetters(String w) { 
    char[] letters = w.toCharArray(); 
    Arrays.sort(letters); 
    return new String(letters); 
} 

的時間複雜度是O(n)其中n是字的假定所有的詞語是大約相同的長度或小上限數，更容易。如果單詞真的很長，這是O（N * log N），其中N是單詞的長度。