Каково время работы этого алгоритма «вычислить все подстроки палиндрома»?

Question

public PriorityQueue<String> findPalindromesSubstring(String string) { 
     PriorityQueue<String> palindromes = new PriorityQueue<>(); 
     string = string.replace("","#"); 
     for (int i = 0; i < string.length(); i++) { //n iterations 
      int j = 0; 
      while (i-j >= 0 && i+j < string.length() && string.charAt(i-j) == string.charAt(i+j)) { 
       String palindrome = string.substring(i-j, i+j+1); 
       if (palindrome.charAt(0) != '#') { 
        palindromes.add(palindrome.replace("#", "")); 
       } 
       j++; 
      } 

     } 
     return palindromes; 
    } 

Я использовал PriorityQueue, потому что мне нужны подстроки палиндром, отсортированные по алфавиту. На данный момент я не забочусь о дубликатах, но я не уверен в худшем случае время работы результат, от моего понимания это что-то вроде

n (chars in string because of for loop)

*

n (max possible length of a palindrome because of inner while loop/2)

*

log(max number of palindromes because of PriorityQueue's add operation)

Так время работы есть O(n^2*logn)? Или я должен заменить одно из n чем-то другим?

Answer 1

Сложность во времени - O(N^3*log(N^2)).
Давайте повнимательнее посмотрим на palindromes.add(palindrome.replace("#", ""));replace функция принимает O(n), add функция делает O(lg N^2) сравнения (потому что мы имеем в большинстве N^2 палиндромов, поэтому высота кучи lg N^2). Каждое сравнение строки принимает O(N), поэтому общее время этой линии O((log N^2) * N + N)