✔ Analyse eines Codes

[Jens K]

hallo zusammen,

ich habe eine kleine Frage.
Ich habe einen kleinen Code:

for (int i = 2; i <= n; i++){
    for (int j = i; j <= n; j = j*i){
        print "Answeisung";
    }
}

Das ist jetzt keine bestimmte Programmiersprache oder so. Ich möchte jetzt gerne analyisieren, wie oft

print "Anweisung"

aufgerufen wird. Wie geht das? das j=j*i überfordert mich etwas

Vielen Dank im voraus

Gruß

 

[Larrywayn]

Gar kein mal oder endlos, weil 1*1 = 1 ist und 1 ist immer gleich 1 oder eben größer, falls n kleiner als 1 ist, und dann bricht es schon vorher ab
Edit: Wie das geht? Einfach mal mit n = 2 z.b. Anfangen und gucken was passiert
schleife 1:
i = 1.
i < 2
schleife 2:
j = i =1.
i < 2 (da sollte vielleicht j hin?)
--ausgabe--
j = 1*1 = 1.
j = i = 1.
i < 2
--ausgabe--
.... usw.

 

[Jens K]

ooh ja genau da hast du recht, da sollte ein j hin und es muss heißen i=2, habe mich verschrieben :-(

also

for (int i = 2; i <= n; i++){
    for (int j = i; j <= n; j = j*i){
        print "Answeisung";
    }
}

 

[sheel]

Mathematische Formel fällt mir auch keine sinnvolle

Höchstens als Ersatz für die innere Schleife
(int)(1/(nlog(i)))
also den ganzzahligen Teil des Kehrwerts vom n-ten Logarithmus von i

Die äussere Schleife zum aufsummieren kommt dann aber noch dazu.

Für sehr größe n ist die Log-Variante vielleicht schneller, als die Doppelschleife

 

[Jens K]

ok. sehr interessant, aber bei mir bleiben noch ein paar Fragen offen?

Wie kommst du auf dieses Ergebnis? und welche Basis hat der Logarithmus?

meintest du die Formel so, wie sie im Anhang steht?

 

[dki]

Hi,
ich komme auf folgendes:

Die Summe von i=2 nach n mit log zur Basis i und dies noch abgerundet.

Als Formel nochmal im Anhang.

Für jedes i wird "print "Answeisung";" ausgeführt, solange

i^x <= n

gilt. x ist dabei immer eine ganze Zahl.

 

[Jens K]

hi,

viele dank für deine Antwort. Sie klingt sehr logisch und man kann sie auch nachvollziehen!! Jetzt muss ich nur noch versuchen die Formel zu verkürzen. Möchte nämlich eine Abschätzung machen, dass dieser Ausdruck kleiner als <= c*n ist. c,n sind natürliche Zahlen

gruß

 

[sheel]

Nein, ich hab nicht n mal, sondern Basis n gemeint.
Aber so wie dki geschrieben hat, kann man sich den Kehrwert auch gleich sparen, ansonsten ist es gleich.

 

[dki]

Naja, wenn du die asymptotische obere Schranke bestimmen willst, dann würde ich es auf O abschätzen.

 

[Jens K]

ja wäre am sinvollsten