Dieses Stück Code ist aus Cracking the Coding Interview Buch.Wie groß ist die Komplexität dieses Zeichenfolgenmanipulationscodes?
public static boolean isUniqueChars2(String str) {
boolean[] char_set = new boolean[256];
for (int i = 0; i < str.length(); i++) {
int val = str.charAt(i);
if (char_set[val]) return false;
char_set[val] = true;
}
return true;
}
Und der Autor erwähnt, dass
Zeitkomplexität O (n) ist, wobei n die Länge der Zeichenfolge ist, und Speicherkomplexität ist O (n).
Ich verstehe Zeitkomplexität O (n) zu sein, aber ich verstehe nicht, wie Speicherkomplexität O sein könnte (n)
Mein Denken: char_set wird ein Array der Größe 256 ganz gleich bleiben, was die Eingabe (str) Größe ist. Auch wenn die Länge von "str" 100.000 ist, ist char_set immer noch ein Array mit 256 Elementen. Also dachte ich, da die Speicheranforderungen für diese Funktion nicht mit der Größe der Eingabe ändern und eine Konstante 256 bleiben, ist die Raumkomplexität konstant, d. H. O (1).
Kann jemand erklären, wenn ich falsch bin (und warum?)
Sie so viel Dank.
Ich denke, Sie haben Recht, aber, dass der Autor sagte, dass die ursprüngliche Str ubupy O (n) (oder Sie erhalten eine Kopie nach Wert?). – qPCR4vir
hmmm ... das ist interessant. Ich dachte, wenn wir asymptotische Komplexitäten ableiten, ignorieren wir im Allgemeinen wie/wo/wann die Eingabe gelesen wird? Und konzentrieren Sie sich nur auf das, was innerhalb der Methode passiert (unter Berücksichtigung der Größe der Eingabe, die ist) – anakkala
Ich möchte die Argumentation des Autors sehen. Der vom Algorithmus selbst genutzte Speicherplatz ist konstant. Sie haben Recht, wenn wir die Komplexität des Raumes analysieren, sprechen wir von der Menge an * zusätzlichem * Platz, die für die Verarbeitung benötigt wird, und ignorieren die Eingabe in den Algorithmus. –