My string is of type"abacsdsdvvsg"
or"a a a a a a a"
And I use String[] stringArray = s.split("");
or String[] stringArray = s.split(" ");
I'm wondering what would be the complexity(in O(string length)
) for above splitting?
PS: I know how to calculate O(…) if code is given. Here I don't know the algorithm of split function.
Java String Functions – Complexity of Java’s String Split Function
javajava8strings
Best Answer
The complexity will depend on the regex that you use to do the splitting. (Yes, the argument you supply to String.split(...) is a regex!)
For your example, it will be
O(N)
whereN
is the number of characters in the input String.The algorithm of split is pretty straight forward, based on an existing regex implementation. A high-level description is:
Matcher.find(...)
to find the next word boundaryThe searching for the breaks between "words" will be
O(N)
or more complex, depending on the regex (thefind
call). The construction of the list, result array and substrings will beO(N)
in the worst case.The precise details are in the source code, which you can find using Google. (Search for
"java.lang.String" source
, pick one and then drill down to the version of Java you are interested in. Or search the files in the source code ZIP file included in your JDK installation)