Quel est le Big-O de String.contains() en Java?

Je travaille sur un projet et j'ai besoin d'optimiser le temps de fonctionnement. Est-ce que String.contains() est identique à TreeSet.contains(), qui est O (logN)?Quel est le Big-O de String.contains() en Java?

La raison pour laquelle je demande est que je construis un TreeMap<String, TreeSet<Song>>, où les chansons contiennent une chaîne de paroles. En fonction de l'efficacité, j'envisage d'inclure un ensemble de mots lyriques dans le morceau et de lancer des recherches sur celui-ci plutôt que sur la chaîne.

Source

2010-11-03 Jason

Ne pas essayer d'être un crétin ou quoi que ce soit, mais: Pourquoi pas le profil? –

Si j'ai le temps pour les tests, peut-être. Il y a un autre test que je veux exécuter avec le projet: les variations d'exécution entre treeet et hashset. S'il y avait 30 heures dans une journée, il n'y aurait toujours pas assez de temps pour tout! – Jason

L'un des algorithmes les plus connus est l'algorithme de recherche de chaînes Boyer-Moore qui est O (n) bien qu'il puisse donner des performances sous-linéaires dans le meilleur des cas.

L'algorithme utilisé en Java dépend de l'implémentation que vous téléchargez. Il semble que par exemple OpenJDK utilise un algorithme naïf qui s'exécute en O (nm) et des performances linéaires dans le meilleur des cas. Voir les lignes 1770-1806 here.

Source

2010-11-03 17:05:12

l'article que vous avez lié à dit c'est O (n) comme il fait au plus 3n comparaisons. "pire cas O (n)" est une tautologie - par définition O (n) est le pire des cas :) –

@Nicholas White: Merci pour la correction. –

Le jdk1.6.0_23 avait la même implémentation 'String.indexOf()' qu'un OpenJDK contemporain, selon https://programmers.stackexchange.com/questions/65558/why-does-javas-string-class-not- implémenter-un-plus-efficace-indexof. Quelqu'un pourrait vous dire si cela est vrai pour 'String.contains()' – rakslice

Vous pouvez également essayer d'utiliser un Trie au lieu d'un TreeMap (bien que Java n'a pas intégré la mise en œuvre Trie)

Source

2010-11-03 17:36:38 dty

[Référence de Trie] (https://www.topcoder.com/community/data-science/data-science-tutorials/using-tries/) – cellepo

Quel est le Big-O de String.contains() en Java?

Répondre

Questions connexes