Временной сложность для зависимых функций

Question

у меня есть этот метод

public static void primeSort(String[] list, HashMap< Integer, ArrayList<String>> hm){ 

    for(int x=0; x<list.length; x++){ 
    if(list[ x ] == null) continue; 

    String curX = list[ x ]; 
    int hashX = primeHash(curX); 

    hm.put(hashX, new ArrayList(Arrays.asList(curX))); 

    for(int y=x+1; y<list.length; y++){ 

     String curY = list[ y ]; 
     int hashY = primeHash(curY); 

     if(curY == null || curY.length() != curX.length()) continue; 

     if(hashX == hashY){ 
     hm.get(hashX).add(curY); 

     list[ y ] = null; // if its an anagram null it out to avoid checking again 
     } 
    } 
    } 
} 

, который вызывает этот метод:

public static int primeHash(String word){ 
    int productOfPrimes = 1; 
    int prime[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 
    37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101 }; 

    for(char ch : word.toCharArray()){ 
    productOfPrimes *= prime[ (int) ch - (int) 'a' ]; 
    } 
    return productOfPrimes; 
} 

Цель состоит в том, чтобы взять список строк и сортировать их в анаграммы, возвращающий список, содержащий анаграммы, сгруппированные в список.

Я пытаюсь определить временную сложность, но это немного сложно. primeSort будет наихудший O (N^2) и лучший случай О (п)

primeHash будет работать m раз каждый раз, когда она называется, где m длина текущей строки. Я не уверен, как это будет проанализировано и как его можно объединить с анализом для PrimeSort.

Любая помощь приветствуется, спасибо :)

Answer 1

Было бы O(n^2) только в первом, так как из вложенного цикла. Затем вы вызываете primeHash один раз в каждом цикле. Там у вас также есть один цикл. Пусть m - длина слова String. Затем в WC вы получите O((n*m)^2). Однако m будет, скорее всего, другим, поэтому я беру самый длинный, скажем M для асимптотического анализа. Также O((n*M)^2). Предполагая, что M в туалете может быть близок к n:

Вы можете в конечном итоге с WC: O((n^2)^2) = O(n^4).

В лучшем случае: у вас есть только одна итерация цикла в первой функции: O(n). Затем мы делаем предположения относительно длины каждого слова. Если они имеют только один символ, то только одна итерация для цикла в primehash или просто постоянна. Поэтому O(1).

BC: O(n).