Asymptotic Komplexität von printf

Unter der Annahme, dass ich eine Zeichenfolge bin Druck wie folgt:Asymptotic Komplexität von printf

printf("%s", s);

Was können wir die asymptotische Komplexität dieser Funktion übernehmen ist?

Ist es O (n) wobei n strlen (s) - es Länge? Oder ist es irgendwie O (1), konstante Zeit. Oder etwas anderes? Ich vermute, dass Sie wissen müssen, wie Printf implementiert wird. Jeder Einblick wird geschätzt!

(Ich sollte klarstellen, dass ich über C rede lieber als C++, aber ich bezweifle, sie sind unterschiedlich implementiert)

Edit: hinzugefügt Formatierungsstring von printf()

Quelle

2013-05-29 Miguel

Die richtige Syntax ist 'printf ("% s ", stringName);'. –

Gibt es einen guten Grund dafür? Schließlich ist s bereits eine Zeichenkette, warum muss sie also mit printf formatiert werden? – Miguel

@Miguel ja, weil _may_ Formatierungscodes selbst enthalten und das wird ein undefined/unbekannt/unberechenbar/wahrscheinlich_very_bad Ergebnis erzeugen. –

Es Komplexität ist O (m + n), wobei m die Größe der Eingabe und n die Größe der Ausgabe ist.

Wenn keine zusätzlichen Parameter übergeben werden wie in Ihrem Fall ist die Zeitkomplexität O (2 * m) = O (m).

Aber bedenken Sie, dass Ihr Code fehlschlagen kann, weil s selbst Formatierungscodes enthalten kann und dass ein undefiniertes/unbekanntes/unvorhersehbares/wahrscheinlich_sehres_Ergebnis ergibt, wie von Adriano hervorgehoben.

Quelle

2013-05-29 15:18:38

Sie sagen also, dass es jedes Zeichen beim Formatieren einmal durchläuft, dann einmal beim Ausgeben? Kann es nicht einfach Speicher zu einem Ausgabestrom ausgeben, oder ist das O (m) überhaupt? – Miguel

Ich dachte immer 'printf' würde die Ergebnisse einfach so ausgeben wie sie ist, wenn sie ein% d' oder ein% s gefunden hat, würde es das passende Argument nehmen und es ausdrucken, daher wäre die Komplexität in der ersten linear Streit. –

@SukritKalra aber Ausdruck einer Zeichenfolge ist nicht O (1). – effeffe

Antwort

Verwandte Themen