Wie komplex ist die String-Split-Funktion von Java?

8

Mein String ist vom Typ "abacsdsdvvsg"oder "a a a a a a a"
Und ich benutze String[] stringArray = s.split("");oder String[] stringArray = s.split(" ");
ich frage mich, wie komplex (in O(string length)) für die obige Aufteilung wäre?
PS: Ich weiß, wie man O (...) berechnet, wenn Code angegeben wird. Hier kenne ich den Algorithmus der Split-Funktion nicht.

java strings java8 tezz
quelle
Mögliches Duplikat von Was ist O (...) und wie berechne ich es?
Mücke
Da ich das Algo der Split-Funktion nicht kenne, denke ich nicht, dass dies eine doppelte Frage ist @gnat
tezz

Antworten:

7

Die Komplexität hängt von der Regex ab, mit der Sie die Aufteilung durchführen. (Ja, das Argument, das Sie String.split (...) geben, ist ein regulärer Ausdruck!)

Für Ihr Beispiel wird es , O(N)wenn Ndie Anzahl der Zeichen in der Eingabe String ist.

Der Split-Algorithmus ist ziemlich einfach und basiert auf einer vorhandenen Regex-Implementierung. Eine allgemeine Beschreibung lautet:

  1. Kompilieren Sie den regulären Ausdruck und erstellen Sie einen Matcher
  2. Iterieren Sie über die Zeichenfolge:
    1. Verwenden Sie Matcher.find(...)diese Option , um die nächste Wortgrenze zu finden
    2. Verwenden Sie String.substring, um das Wort zu extrahieren
    3. Fügen Sie einer Liste von Zeichenfolgen ein Wort hinzu
  3. Konvertieren Sie die Liste der Zeichenfolgen in ein Array von Zeichenfolgen.

Die Suche nach den Unterbrechungen zwischen "Wörtern" O(N)ist je nach Regex (dem findAufruf) oder komplexer . Die Erstellung der Liste, des Ergebnisarrays und der Teilzeichenfolgen erfolgt O(N)im schlimmsten Fall.

Die genauen Details finden Sie im Quellcode, den Sie über Google finden. (Suchen Sie nach einer "java.lang.String" source, wählen Sie eine aus und führen Sie einen Drilldown zu der Java-Version durch, an der Sie interessiert sind. Oder durchsuchen Sie die Dateien in der ZIP-Datei des Quellcodes, die in Ihrer JDK-Installation enthalten ist.)

Stephen C.
quelle
3

Es ist O (n) in Ihren speziellen Fällen, in denen Sie durch Trennzeichen mit einer Länge von 1/0 Zeichen teilen. Im Allgemeinen ist es O (n + k) mit einem k-Zeichen-Trennzeichen, das mit dem KMP-Algorithmus implementiert werden kann. Java String Split akzeptiert auch reguläre Ausdrücke als Trennzeichen. In diesem Fall hängt die Komplexität vom verwendeten Matching-Algorithmus ab. Ein üblicher Regex-Matching-Algorithmus ist der Thompson NFA-Algorithmus.

VinyleEm
quelle