Große O-Effizienz für mehrere Variablen

Question

Ich versuche, die Effizienz einer Funktion zu bewerten, wo die Eingabe ein Array von Strings ist. Der Algorithmus durchläuft immer alle Elemente in diesem Array. Diese in diesem Array enthaltenen Strings haben eine variable Länge. In dieser initialen for-Schleife wird eine Zeichenersetzungsfunktion für jede Zeichenfolge aufgerufen. Ich glaube, die Replace-Funktion wäre O (n), wobei n die Länge der Zeichenkette ist.

So bin ich verwirrt, wie man große o Effizienz hier bewertet. Wenn n die Größe des Arrays ist, weiß ich, dass es mindestens O (n) sein wird. Aber wie würden Sie bei variablen Stringlängen die Gesamteffizienz bei der String-Ersetzung bewerten? Würden Sie sagen, dass n die Größe des Arrays ist und andere Variablen verwenden, um die verschiedenen Größen der einzelnen Strings darzustellen?

Answer 1

Ich sehe zwei Möglichkeiten, dies zu sagen (von vielen möglichen).

Die erste ist zu sagen, es ist O(N) wo N ist die Gesamtzahl der Zeichen.

Die andere könnte man sagen ist O(N*M) wo N ist die Anzahl der Zeichenfolgen und M ist die durchschnittliche Anzahl der Zeichen pro Zeichenfolge. Beachten Sie, dass dies tatsächlich meine obige Antwort ist. Sie könnten sagen M = k/N, so erhalten Sie O(N*k/N) oder O(k) wo k ist die Gesamtzahl der Zeichen in allen Zeichenfolgen.

Answer 2

Persönlich würde ich Effizienz durch Größe der Eingabedaten (im Gegensatz zu der Länge der Array) auszudrücken. Wenn die Eingabe also t Bytes ist, wird die Laufzeit O(t) sein. Und t hier ist auch eine gemeinsame Länge aller Zeichenfolgen.