На)??? Может ли кто-нибудь сказать мне большой O из .reverse

скажем, я использую следующие методы для поиска палиндрома. Я знаю, что первый - O (n), потому что он проходит через всю строку. Выполняет ли .reverse() в StringBuffer также O(n)? Я не беспокоюсь о том, чтобы найти лучший способ решить проблему. Я пытаюсь понять, физически ли обратный метод переворачивает строку или он намного эффективнее этого? Спасибо

public static boolean isAPalindrome(String s1){

    String tmp = "";    
    int length = s1.length();
    for(int i = 0; i < s1.length(); i++){           
        tmp += s1.charAt(s1.length()-i-1);
    }       
    if (s1.equals(tmp)) return true;
    return false;           

}

public static boolean isAPalindrome(String s1){

    StringBuffer a = new StringBuffer(s1);
    return s1.equals(a.reverse().toString());

}

java string big-o stringbuffer
person Matthew Leighty    schedule 20.01.2016    source источник
comment
stackoverflow.com/questions/2439141/   -  person novice    schedule 20.01.2016
comment
Привет, Мэтью, если ответ решил ваш вопрос, примите его, нажав зеленую галочку рядом с ним. Спасибо   -  person Idos    schedule 21.01.2016

Ответы (2)


arrow_upward
0
arrow_downward

Вы можете реализовать реверс, который эффективно o(1), но не с типичными строковыми классами: вы можете сделать это, реализовав строковый класс с элементом направления, который может принимать значения «вперед» или «назад». Но это имело бы смысл только в том случае, если бы возврат преобладал над вашей производительностью над всеми другими вычислениями.

person Dirk Herrmann    schedule 20.01.2016

arrow_upward
0
arrow_downward

Обратное преобразование строки не может быть быстрее, чем O(n) (при нормальном представлении строки).
Вы должны "действовать" над каждым символом строки, поэтому теоретически это не может быть быстрее.

StringBuffer расширяет AbstractStringBuilder, который реализует reverse. Вы можете самостоятельно просмотреть исходный код здесь.

Примечание: это не означает, что StringBuilder/Buffers reverse будет работать так же быстро, как метод O(n) reverse, который вы напишете. Вероятно, он будет работать гораздо быстрее. Но асимптотически это все равно будет O(n).

person Idos    schedule 20.01.2016
comment
Это, если вы реверсируете проблему, которая должна проверить либо решение, либо что-то еще, это то же самое и не лучше. Просто другое решение без наследуемого преимущества. - person jgr208; 20.01.2016
comment
Это просто неправда. У вас вполне может быть структура данных для строк с обратной операцией с постоянным временем. - person Emil Vikström; 21.01.2016
comment
@EmilVikström хочешь уточнить? ОП, очевидно, не спрашивал о каких-либо неясных представлениях строк. Любой нормальный потребует как минимум O(n). - person Idos; 21.01.2016
comment
Вы сказали, что это не может быть быстрее. Ответ Дирка предоставляет возможный способ сделать это быстрее (двухсвязный список с флагом направленности). Это не имеет значения для OP, поскольку у них все еще есть проверка на равенство, которая выполняется за O (n), но на самом деле это не вопрос. Здесь нет тега языка, поэтому я предполагаю, что вопрос касается алгоритмов и структур данных, а не конкретных реализаций. - person Emil Vikström; 21.01.2016
comment
Я просто категорически не согласен. Я мог бы конечно написать язык, в котором любая операция по вашему выбору будет o(1), но это было бы бесполезно. Строковый список в его обычном представлении не может быть обращен за O(n) по очевидным причинам (и я указал некоторые из них). И также очевидно, что вопрос касается Java, поскольку он разместил код Java. - person Idos; 21.01.2016
comment
В любом случае я немного отредактировал свой ответ, чтобы придерживаться обычного стандарта. - person Idos; 21.01.2016