Che cos'è il Big-O di String.contains() in Java?

Sto lavorando a un progetto e ho bisogno di ottimizzare il tempo di esecuzione. Il tempo di esecuzione String.contains() è lo stesso di TreeSet.contains(), che è O (logN)?Che cos'è il Big-O di String.contains() in Java?

Il motivo per cui sto chiedendo è che sto creando un TreeMap<String, TreeSet<Song>>, dove le canzoni contengono una stringa di parole. A seconda dell'efficienza, sto considerando di includere un Set delle parole dei testi all'interno della Song e di eseguire ricerche su questo piuttosto che sulla stringa.

fonte

2010-11-03 Jason

Non cercare di essere un coglione o qualcosa, ma: Perché non il profilo it? –

Se ho tempo per le prove, forse. C'è un altro test che voglio eseguire con il progetto: variazioni di runtime tra il set di alberi e l'hashset. Se ci fossero 30 ore in un giorno, non ci sarebbe ancora abbastanza tempo per tutto! – Jason

Uno degli algoritmi più noti è l'algoritmo di ricerca stringa Boyer-Moore che è O (n) anche se può fornire prestazioni sublimate nel migliore dei casi.

Quale algoritmo viene utilizzato in Java dipende da quale implementazione viene scaricata. Ad esempio, OpenJDK ad esempio utilizza un algoritmo ingenuo eseguito in O (nm) e prestazioni lineari nel migliore dei casi. Vedere le linee 1770-1806 here.

fonte

2010-11-03 17:05:12

l'articolo che hai collegato per dire che è O (n) poiché effettua al massimo 3n confronti. "worst case O (n)" è una tautologia - per definizione O (n) è il caso peggiore :) –

@Nicholas White: Grazie per la correzione. –

jdk1.6.0_23 aveva la stessa implementazione 'String.indexOf()' come OpenJDK contemporaneo, in base a https://programmers.stackexchange.com/questions/65558/why-does-javas-string-class-not- implement-a-more-efficient-indexof. Qualcuno potrebbe dirti se questo è vero per 'String.contains()' – rakslice

Si potrebbe anche provare a utilizzare un trie al posto di un TreeMap (anche se Java non ha incorporato implementazione Trie)

fonte

2010-11-03 17:36:38 dty

[riferimento Trie] (https://www.topcoder.com/community/data-science/data-science-tutorials/using-tries/) – cellepo

Che cos'è il Big-O di String.contains() in Java?

risposta

Problemi correlati