Я работаю над проектом и должен оптимизировать время работы. Является ли String.contains() время выполнения таким же, как TreeSet.contains(), которое является O (logN)?
Причина, по которой я спрашиваю, это создание TreeMap<String, TreeSet<Song>>, где Песни содержат строку текстов. В зависимости от эффективности, я рассматриваю возможность включения набора лирических слов внутри песни и выполнения поисков на этом, а не на String.
Одним из наиболее известных алгоритмов является поисковый алгоритм Boyer-Moore, который является O (n), хотя он может дать сублинейную производительность в лучший случай.
Какой алгоритм используется в Java, зависит от того, какую загрузку вы загружаете. Похоже, что OpenJDK использует наивный алгоритм, который работает в O (nm) и линейной производительности в лучшем случае. См. Строки 1770-1806 здесь.
Вы также можете попробовать использовать Trie вместо TreeMap (хотя Java не имеет встроенной реализации Trie)