O-Notation und Zahl versus String-Repräsentation

[Ark]

Ich frage mich, wie aufwendig die Berechnung der String-Repräsentation einer Zahl bzw. der Zahl aus einer String-Repräsentation eigentlich ist.

Wenn ich die Zahl z zur Berechnung ansetze, dann komme ich zum Schluss, dass ihre String-Repräsentation S mit O(log n) (oder besser O(log z)) ermittelt werden kann. Nehme ich aber |S|, also die Länge von S, dann komme ich auf linearen Aufwand. Dem gegenüber gibt es aber die Potenz eines Wortes, und der Zusammenhang zwischen der Länge des erzeugten Wortes, der des ursprünglichen Wortes und dem Exponenten, nämlich

|w^n| = n * |w|

lässt eher einen logarithmischen Zusammenhang vermuten. Was stimmt denn nun? Oder bin ich komplett auf dem Holzweg?

Ark

 

[Marco13]

Wenn ich die Zahl z zur Berechnung ansetze, dann komme ich zum Schluss, dass ihre String-Repräsentation S mit O(log n) (oder besser O(log z)) ermittelt werden kann. Nehme ich aber |S|, also die Länge von S, dann komme ich auf linearen Aufwand.

Das hängt wohl schlicht und einfach damit zusammen, dass die Länge einer Zahl logarithmisch zu ihrer Größe ist... ???:L (oder ist mein Koffeinmangel gerade SO akut?)

Wie die Potenz damit zusammenhängt, ist mir aber nicht ganz klar... deine Formel
|w^n| = n * |w|
an einem Beispiel
|11^2| = 2 * |11|
stimmt ja nicht so ganz... (oder ich hatte sie falsch interpretiert)

Ich würde spontan tippen, dass der Aufwand logarithmisch im bezug auf die Größe der Zahl ist - und zwar der Logarithmus zur Basis b, wenn in einen b-ale Zahl-String umgewandelt werden soll...

 

[Ark]

Wie die Potenz damit zusammenhängt, ist mir aber nicht ganz klar... deine Formel
|w^n| = n * |w|
an einem Beispiel
|11^2| = 2 * |11|
stimmt ja nicht so ganz... (oder ich hatte sie falsch interpretiert)

Du musst 11 eher als "11" lesen, also als Zeichenkette mit 2 Zeichen. In deinem Beispiel könnte man eben sagen

floor(log(11)) = |"11"| - 1 = 1

Vielleicht ist es aber besser, stattdessen das so zu schreiben:

ceil(log(11)) = |"11"| = 2

Was das Logarithmusgesetz

log(a^b) = b * log(a)

angeht, kommt man auf vergleichbare Ergebnisse über die String-Repräsentation von a, wenn man a selbst als Basis des Logarithmus ansetzt. Dann sieht a nämlich immer nach "1" aus, und "1" ^ b erzeugt ein Wort mit b vielen Einsen. (Man könnte sich auch direkt auf die Länge des Wortes berufen, wenn man den konstanten Faktor zur Änderung der Logarithmusbasis berücksichtigt.) Zumindest aus der Sicht erscheint es mir logisch, dass man das Konstrukt in Bezug auf das Wort eben Potenz und nicht Multiplikation nennt. PENPEN ist eben PEN² und nicht PEN*2. Die Länge des Wortes kann man dann auch mit dem Logarithmus vergleichen.

Meine Ausgangsfrage ist damit allerdings noch immer nicht geklärt. Ist der Aufwand zur Berechnung der String-Repräsenation aus einer Zahl (bzw. anders herum) nun logarithmisch (in Bezug auf die Größe der Zahl) oder linear (in Bezug auf die Länge des erzeugten Strings)? Oder ist die Länge eines Strings selbst schon eine logarithmische Größe?

Ark

 

[Leroy42]

Verstehe ich g'rad überhaupt nix oder stehe ich
nur auf dem Schlauch? :shock:

Komisch, habe doch gestern gar nix getrunken? ???:L

 

[Marco13]

Oh ja, das mit dem Exponenten hatte ich fehlinterpretiert. Aber....

Ist der Aufwand zur Berechnung der String-Repräsenation aus einer Zahl (bzw. anders herum) nun logarithmisch (in Bezug auf die Größe der Zahl) oder linear (in Bezug auf die Länge des erzeugten Strings)? Oder ist die Länge eines Strings selbst schon eine logarithmische Größe?

Die Fragen würde ich alle drei mit "JA" beantworten. (Die Darstellung im "Einersystem" ist ein Sonderfall).
- Die Länge eines Strings ist selbst schon eine logarithmische Größe
- Der Aufwand zur Berechnung der String-Repräsenation aus einer Zahl ist linear in bezug auf die Länge des erzeugten Strings
==> Der Aufwand zur Berechnung der String-Repräsenation aus einer Zahl ist linear in bezug auf die Größe der Zahl

 

[Ark]

Hm, eine kleine Ungenauigkeit meinerseits: a sieht zur Basis a immer wie "10" aus, und der Logarithmus von a zur Basis a ist immer 1. Das durch die Potenz erzeugte Wort ist also doppelt so lang (wegen dieser 1 in "10", der Betrag des Wortes im Vergleich zur Logarithmusfunktion ist ja auch um 1 verschoben), aber das ist ja wieder nur ein konstanter Faktor. Außerdem kann man die Länge des Wortes nur sehr angenähert zur Berechnung des Logarithmus nehmen, weil sie für gleich "lange" Zahlen gleiche Ergebnisse liefert.

@Marco13: Und welche Zeitkomplexität würdest du für parseInt() bzw. toString() ansetzen? O(log n) oder O(n)? Oder ist parseInt() der Art O(n) und toString() der Art O(log n)? Oder wie?

Ark

 

[Marco13]

Ich würde aus oben genannten Gründen in beiden Fällen auf O(log(n)) tippen: Man hantiert ja nur mit den Stellen der Zahl, und die Anzahl der Stellen ist logarithmisch für die Zahl selbst.

 

[0x7F800000]

Also, ich würde noch anmerken, dass die Ausgabe in Binär /Oktal / Hexadezimaldarstellung praktisch nichts kostet, weil bitshifts wesentlich billiger sein dürften, als divisionen, die bei der p-adischen Entwicklung zur basis p != 2^k notwendig sind.
In diesem Fall (also bei p!= 2^k) sind bei der Zahl n log_p(n) divisionen notwendig, der Aufwand beim darstellen als zeichenkette ist also O(log_p(n))=O(log(n)).

In die andere Richtung läuft es dagegen in linearer zeit im bezug auf die Länge der Zeichenkette.
D.h. für eine Zeichenkette der Länge L sind 2L multiplikationen und additionen nötig, der Aufwand ist also O(L).

Das ist aber nur "scheinbar" langsamer als die p-adische entwicklung, denn aus einer Zeichenkette der Länge L wird ja auch eine Zahl der größenordnung p^L.

Also ist das darstellen als Zeichenkette eigentlich eine recht teuere Angelegenheit, wenn man irgendeine schleife laufen lässt, und zum test bei jedem durchlauf irgendeine Zahl ausgibt, braucht man sich nicht zu wundern, dass die "debug"-ausgabe wesentlich mehr kostet, als die eigentliche ausführung des Programms.



Aber das hat Marco13 ja alles schon gesagt, ich wollte das nur nochmal mit O(L) statt O(n) hinschreiben, weil's ansosnsten evtl nicht ganz klar ist, worauf sich das n bezieht