这个 "compute all palindrome substrings" 算法的运行时间是多少？

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)

这个 "compute all palindrome substrings" 算法的运行时间是多少？

What's the running time of this "compute all palindrome substrings" algorithm?

algorithm

priority-queue

palindrome

这个 "compute all palindrome substrings" 算法的 运行 时间是多少？

What's the running time of this "compute all palindrome substrings" algorithm?

algorithm

priority-queue

palindrome

这个 "compute all palindrome substrings" 算法的运行时间是多少？