Stringvergleich
-
Heyho,
ich hätte eine kleine Frage zu einem Stringvergleich. Angenommen, man hat einen String von einer Länge die 60.000 Stellen entspricht und man will diesen String mit einem anderen String gleicher Länge vergleichen. Kommt die gleiche Zeit raus, wenn man einen String mit einer Länge von 3 mit einem anderen der Länge 3 vergleicht, als wenn einen mit einer Länge von 60.000 mit einem anderen der Länge 60.000 vergleicht? Und wenn nicht, wie sieht der Zeitunterschied aus?
Mfg
-
> Kommt die gleiche Zeit raus, wenn man einen String mit einer Länge von 3 mit einem anderen der Länge 3 vergleicht, als wenn einen mit einer Länge von 60.000 mit einem anderen der Länge 60.000 vergleicht?
Kurz: Nein
Lang: Aber die benötigte Zeit ist ungefähr direkt proportional zur Stringlänge. Da du in diesem Algorithmus auf jeden Fall jedes der Zeichen prüfen musst entspricht der Worst-Case dem Best-Case, der Zeitkomplexität O(n) mit n = |string|. Die Komplexität ist immer gleich. In Realität multiplizierst du jetzt noch einen Faktor drauf, der die Geschwindigkeit deiner Maschine präsentiert. Je mehr String, desto mehr Zeit.
-
Warum sollte man in beiden Fällen jedes Zeichen prüfen müssen? Sofern sich ein Zeichen unterscheidet, kann es keine Übereinstimmung mehr geben. Ist also bei einem String der Länge 60.000 das erste Zeichen bereits unterschiedlich brauchen alle folgenen Zeichen nicht mehr überprüft werden.
-
Ad aCTa schrieb:
Da du in diesem Algorithmus auf jeden Fall jedes der Zeichen prüfen musst entspricht der Worst-Case dem Best-Case
Nene. Wenn die Strings an erster Stelle unterschiedlich sind, muss ich die restlichen 59999 nicht mehr anschauen.
-
Also braucht man schimmstenfalls 60.000 Zeiteinheiten. Aber bestenfalls nur eine.
Falls die Strings ganz zufällig sind, auch nur im Durchschnitt ungefähr eine.
Falls sie sowas wie Dateipfade sind, wo sauoft gleiche Verzeichnisse sind, dauert's im Durchschnitt viel länger als nur eine. Aber ich habe keinen Schimmer, ob das "viel länger" typischerweise eher 10 oder eher 1000 ist. Schade. Leider habe ich heute keine Zeit, es bei mir mal auszumessen. Ich sehr neugierig bin.
-
Bei Dateipfaden, die sich eher gegen Ende unterscheiden, könnte man auch von hinten vergleichen. Bei einem anderen Anwendungsfall will man vielleicht zuerst nur jedes 10. Zeichen vergleichen und springt so durch den String.