Блог

Главная - Вопросы по программированию - Невозможно определить временную сложность

Невозможно определить временную сложность

#java #time-complexity

#java #временная сложность

Вопрос:

Итак, я должен разделить входную строку на 3 палиндромные подстроки. Это решение, которое было дано, и хотя я хорошо его понимаю, мне трудно определить его временную сложность. Вот код:

     public static boolean isPallindrome(String str){
        StringBuffer sb = new StringBuffer(str);
        return str.equals(sb.reverse().toString());
    }

    public static void func(String s){
        for(int i = 1; i < s.length() - 2; i  ){
            if (isPallindrome(s.substring(0, i))){
                for(int j = i 1; j < s.length(); j  ){
                    if (isPallindrome(s.substring(i, j)) amp; isPallindrome(s.substring(j))){
                        System.out.print(s.substring(0, i).trim()   "n"   s.substring(i, j).trim()   "n"   s.substring(j, s.length()).trim());
                        return;
                    }
                }
            }
        }

Какова временная сложность func функции?

Я думаю, что это будет O (n ^ 2), но я не уверен.

Для такого новичка, как я, было бы действительно полезно, если бы временная сложность этой функции была должным образом объяснена. Спасибо.

Комментарии:

1.Как вы думаете, почему это O (n ^ 2)? В худшем случае входная строка n в разы превышает одну и ту же букву, например, func("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa") has n = 40 , и каждый вызов isPallindrome() в коде вернет значение true. Итак, если вы думаете, что код состоит только из O (n ^ 2), вы не учитываете временную сложность isPallindrome() вызова, которая, безусловно, не O (1).

2. О, теперь я это понимаю. Означает ли это, что временная сложность будет равна O (n ^ 3)?

3. Больше похоже на O (n ^ 4) , не так ли?

4. О, я вижу, поскольку существует несколько вызовов isPallindrome() в 2 разных циклах. Есть ли какой-либо способ уменьшить временную сложность? Мне трудно оптимизировать.