Временная сложность O () isPalindrome ()

Question

У меня есть этот метод isPalindrome (), и я пытаюсь найти его временную сложность, а также более эффективно переписать код.

boolean isPalindrome(String s) {
    boolean bP = true;
    for(int i=0; i<s.length(); i++) {
        if(s.charAt(i) != s.charAt(s.length()-i-1)) {
            bP = false;
        }
    }
    return bP;
}

Теперь я знаю, что этот код проверяет символы строки, чтобы определить, совпадает ли она с предыдущей, и если это так, то она не изменит bP.

И я думаю, что я знаю, что это операции s.length (), s.charAt (i) и s.charAt (s.length () - i -!)).

Как мне кажется, сложность по времени O (N + 3)? Это правильно, если не то, что это и как это выяснить.

Также, чтобы сделать это более эффективным, было бы хорошо хранить символ во временных строках?

Answer 1

Это просто O (N).

Сказать O (N + 3) не имеет смысла - постоянные факторы игнорируются.

Вы можете сделать это быстрее, если обнаружите несоответствие:

bP = false;
break;

(Не то чтобы это изменило тот факт, что это O (N), но это ускорит его в большинстве случаев.)

Это не правда:

этот код проверяет символы строки, чтобы определить, совпадает ли она с предыдущей

Он проверяет, совпадают ли символы в начале с теми, что в конце, иными словами, это наивный палиндром проверка.

Другое ускорение будет повторяться до s.length()/2 - в противном случае вы выполняете все сравнения дважды для строки, которая является палиндромом.

Answer 2

Данный код, кажется, проверяет, является ли строка палиндромом, проверяя, совпадает ли символ «N» с символом «длина-N». Как уже упоминалось, вы можете увеличить эффективность на

• только проверка первой половины
• вспыхивает (возвращает false), как только вы обнаружите несоответствие

К этим предложениям я бы добавил

• не пересчитывать s.length () повторно каждый раз в цикле, поскольку он не изменяется.

Учитывая все это:

boolean isP(String s) {
  int l = s.length();
  int l2 = l/2;
  int j = l - 1;
  for(int i=0; i<l2; i++) {
    if(s.charAt(i) != s.charAt(j)) {
        return false;
    }
    j--;
  }
  return true;
}

Answer 3

Скорее всего, это наиболее эффективная реализация в Java:

    public static boolean isP(String s) {
        char[] chars = s.toCharArray();
        for (int i = 0; i < (chars.length / 2); i++) {
            if (chars[i] != chars[(chars.length - i - 1)])
                return false;
        }
        return true;
    }

Преимущества:

• Возвращается с первого взгляда на разницу.
• Использует прямой доступ к char [], чтобы избежать дополнительных проверок, выполняемых в charAt
• Итерирует только половину строки, в отличие от полной строки.

Это, как и все другие предложенные решения, все еще O (N).

Я только что измерил времена для представленных решений для действительно большой строки (времена в наносекундах):

 Aran:           32244042
 Andreas:        60787894
 Paul Tomblin:   18387532

Во-первых, вышеупомянутые измерения были выполнены с клиентской виртуальной машиной . Таким образом, расчет i < (chars.length / 2) не был встроен как константа. Использование параметра -server Vm дало намного лучший результат:

 Aran:           18756295
 Andreas:        15048560
 Paul Tomblin:   17187100

Чтобы сделать его немного экстремальным:

---

Сначала предупреждающее слово: НЕ ИСПОЛЬЗУЙТЕ ЭТОТ КОД В ЛЮБОЙ ПРОГРАММЕ, КОТОРОЙ ВЫ НАМЕРЕНЫ ИСПОЛЬЗОВАТЬ / ПЕРЕВОЗИТЬ.

---

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

Существуют некоторые издержки при копировании массива из строки, поскольку класс строки внутренне создает защитную копию.

Если мы получим исходный символ [] из строки напрямую, мы сможем выжать немного производительности за счет использования операций отражения и несохранения над строкой. Это дает нам еще 20% производительности.

public static boolean isPReflect(String s) {
    char[] chars = null;
    try {
        final Field f = s.getClass().getDeclaredField("value");
        f.setAccessible(true);
        chars = (char[]) f.get(s);
    }
    catch (IllegalAccessException e) {
    }
    catch (NoSuchFieldException e) {
    }

    final int lenToMiddle = chars.length / 2;
    for (int i = 0; i < lenToMiddle; i++) {
        if (chars[i] != chars[(chars.length - i - 1)]) 
            return false;
    }
    return true;
}

Times:

 Aran:           18756295
 Andreas1:       15048560
 Andreas2:       12094554
 Paul Tomblin:   17187100

Answer 4

Вот еще одно решение с двумя противоположными указателями:

boolean isPalindrome(String s) {
    int i = 0, j = s.length() - 1;
    while (i < j && s.charAt(i) == s.charAt(j)) {
        ++i;
        --j;
    }
    return i >= j;
}

Сложность снова O ( n ).

Если вдаваться в подробности: скажем, каждая операция стоит 1 единицу. Сравнения, присваивания, арифметические операции, вызовы функций каждого стоят 1 единицу. Поэтому вызов isPalindrome стоит в худшем случае (s - палиндром), например:

  4 + n/2 · (3 + 4) + 1
= 5 + n/2 · 7
= 5 + 7/2 · n

И так как постоянный коэффициент (здесь 5 + 7/2) опущен, мы получаем 5 + 7/2 · n ∈ O ( n ). * * тысячу двадцать-один

Answer 5

Это O (N). Вы делаете N сравнений, где N = s.length (). Каждое сравнение занимает O (1) времени, так как это сравнение одного символа.

+ 3 не имеет значения, поскольку асимптотическая запись относится только к члену высшего порядка.

Answer 6

Во-первых, не может быть однопоточного решения этой проблемы, где сложность "наихудшего случая" лучше, чем O(N) для произвольных входных строк. Проще говоря, любой алгоритм должен смотреть на каждый символ в строке в худшем случае. Теоретически вы можете улучшить O(N), используя аппаратный параллелизм; то есть имеют бесконечно масштабируемое количество процессоров, работающих на разных частях строки. На практике было бы трудно добиться какого-либо ускорения вообще. Стоимость отправки входной строки (или соответствующих частей) каждому процессору будет равна 'O (N)', если только у меня нет решения, о котором я не знаю.

Во-вторых, как видите, поведение O(N) не является окончательным ответом. Вы также должны рассмотреть мультипликативную константу как N -> бесконечность, и меньшие члены для меньших значений N.

В-третьих, @dfa говорит, что микро-оптимизация не в вашем бизнесе. Он на правильном пути, но я не думаю, что это так ясно. ИМО, микрооптимизация - пустая трата времени, если 1) ваше приложение действительно не должно работать как можно быстрее, и 2) ваше профилирование приложения показывает, что этот конкретный расчет действительно является значительным узким местом.

Наконец, микрооптимизация, которая делает программу быстрее для одной конкретной аппаратной платформы / JIT-компилятора, может замедлить ее для другой. Сложный микрооптимизированный код сложнее для JIT-компилятора, чтобы создать эффективный код. И если вы используете отражение для доступа к внутренним элементам (скажем) класса String, ваш код может фактически потерпеть неудачу на некоторых платформах. (Ничто в спецификации библиотеки классов Java не говорит о том, что строка имеет закрытое поле с именем «значение», которое является char[] !!!)

Answer 7

Итак, во-первых, что должен делать метод?

Мое предположение: определите, является ли строка палиндромом .

Совершенно очевидно, что вы не сможете получить его ниже O (N):

O(N+3) == O(N)

Другой вопрос, это самое эффективное решение? Возможно нет.

Комната для улучшения:

1. Разрежьте его пополам. Вы проверяете всех персонажей два раза (как предложил Михил Буддинг).

2. Получить массив символов заранее. Это избавляет вас от некоторых проверок индекса, которые происходят внутри chatAt().

Все остальные операции, charAt() и length(), являются O (1) со стандартной реализацией String.

Answer 8

Или вы можете просто сделать

def isPalindrome?(x)
 return x == x.reverse
end

Это все еще O (n) сложность времени.

Answer 9

Если предположить, что операции в вашем цикле могут выполняться за постоянное время, сложность составляет O (N). Поскольку нотация «Big-O» измеряет рост, а не чистую скорость, постоянные факторы могут не учитываться. Это оставляет нас с выводом, что O (N + 3) равно O (N).

Answer 10

Большая O сложность всегда без затрат (поскольку для N-> oo они не важны). Таким образом, сложность вашего времени просто O(n).

Кроме того, чтобы сделать это более эффективным, было бы хорошо хранить символ во временных строках?

Это не твоя работа. JIT-компилятор справится с этой микрооптимизацией за вас.