La mia stringa è di tipo "abacsdsdvvsg" o "a a a a a a a"
E io uso String[] stringArray = s.split(""); o String[] stringArray = s.split(" ");
Mi chiedo quale sarebbe la complessità (in O(string length) ) per la suddetta divisione?
PS: So come calcolare O (...) se viene dato il codice. Qui non conosco l'algoritmo della funzione split.
La complessità dipenderà dalla regex che si usa per eseguire la divisione. (Sì, l'argomento che fornisci a String.split (...) è un'espressione regolare!)
Per il tuo esempio, sarà O(N) dove N è il numero di caratteri nella stringa di input.
L'algoritmo di divisione è abbastanza semplice, basato su un'implementazione di espressioni regolari esistente. Una descrizione di alto livello è:
Matcher.find(...) per trovare il prossimo limite di parole La ricerca delle interruzioni tra "parole" sarà O(N) o più complesse, a seconda della regex (la chiamata find ). La costruzione dell'elenco, matrice dei risultati e sottostringhe sarà O(N) nel caso peggiore.
I dettagli precisi sono nel codice sorgente, che puoi trovare usando Google. (Cerca "java.lang.String" source , sceglierne uno e poi esegui il drill down sulla versione di Java che ti interessa. Oppure cerca i file nel file ZIP del codice sorgente incluso nell'installazione di JDK)
È O (n) nei tuoi casi particolari, dove stai dividendo per separatori di lunghezza carattere 1/0. In generale, è O (n + k) con un separatore di caratteri k, può essere implementato usando l'algoritmo KMP. Lo split string di Java accetta anche espressioni regolari come seperators, nel qual caso la sua complessità dipende dall'algoritmo di matching utilizzato. Un algoritmo di corrispondenza regex comune è l'algoritmo NFA Thompson.