Какова временная сложность следующего кода?

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 - длина слов.