Что такое Big-O String.contains () в Java?

Question

Я работаю над проектом, и мне нужно оптимизировать время выполнения.Является ли String.contains() время выполнения таким же, как TreeSet.contains(), то есть O (logN)?

Причина, по которой я спрашиваю, состоит в том, что я создаю TreeMap<String, TreeSet<Song>>, где песни содержат строку текста.В зависимости от эффективности я рассматриваю возможность включения в текст песни набора лирических слов и проведения поиска по нему, а не по строке.

Answer 1

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

Какой алгоритм используется в Java, зависит от того, какую реализацию вы загружаете. Кажется, что, например, OpenJDK использует наивный алгоритм, который работает в O (нм) и линейной производительности в лучшем случае. Смотрите строки 1770-1806 здесь .

Answer 2

Вы также можете попробовать использовать Trie вместо TreeMap (хотя в Java нет встроенной реализации Trie)