Какова временная сложность .equals в java для 2 строк?

Мне было интересно, что сложность времени (большой O) оператора .equals в Java была для двух строк.

В принципе, если я сделал stringOne.equals(stringTwo), насколько хорошо это работает?

Спасибо.

Ответ 1

В худшем случае O (n), если только две строки не являются одним и тем же объектом, в этом случае O (1).

(Хотя в этом случае n относится к числу совпадающих символов в двух строках, начиная с первого символа, а не по всей длине строки).

Ответ 2

Другие ответы здесь чрезмерно упрощены.

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

Однако это всего лишь худший случай: есть много ярлыков, которые означают, что метод equals() может работать намного лучше, чем это, в среднем/типичном случае:

Это O(1), если строки одинаковы: они одинаковы по общему объекту, поэтому результат верен.
Это O(1), если вы можете проверить предварительно вычисленные хэш-коды, которые могут доказать, что две строки не равны (очевидно, это не может доказать, что две строки равны, потому что многие хеши строк имеют один и тот же хэш-код).
It O(1), если строки имеют разную длину (они не могут быть равны, поэтому результат является ложным)
Вам нужно только обнаружить один другой символ, чтобы доказать, что строки не равны. Таким образом, для случайных распределенных строк это обычно среднее время O(1) для сравнения двух строк. Если ваши строки не являются полностью случайными, результат может быть где-то между O(1) и O(n) в зависимости от распределения данных.

Как вы можете видеть, точная производительность зависит от распределения данных.

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

Окончательный трюк: если вы используете Интерпретация строки, то все равные строки будут сопоставлены с одним экземпляром объекта. Затем вы можете использовать чрезвычайно быструю проверку == для идентификации объекта вместо equals(), которая гарантированно будет O(1). Этот подход имеет свои недостатки (вам может потребоваться ставить много строк, вызывая проблемы с памятью, и вам нужно строго помнить, чтобы ставить любые строки, которые вы планируете использовать с этой схемой), но в некоторых ситуациях это чрезвычайно полезно.

Ответ 3

Это легко возможно в O (n) и невозможно в меньшем, чем то, что должно быть.