Wie kann man man die Laufzeit dieser Programmen bestimmen?

...komplette Frage anzeigen

3 Antworten

Ich nehme an, n ist der Parameter. Die Schleife 1.1 wird k-mal durchlaufen. Das musst Du sehen. Was steht hinteher in j? Die summe der Zahlen von 1 bis n. n muss dabei ein Parameter sein, der übergeben wird, denn n wird nicht initialisiert und würde in einem echten C-Programm auf einem zufälligen Wert stehen.

Auf welchen Werten stehen i und j am Ende der ersten Schleife?

Die zweite Schleife wird j-mal durchlaufen, das solltest Du auch sehen. Es werden jeweils i+j-k ausgegeben. Nur k ist veränderlich.

Nach dem System die anderen beiden Aufgaben angehen und dabei die Syntaxfehler ignorieren ;-).

trotzdem habe ich nicht verstanden,

kannst Du unten gucken, ich habe das neu gedruckt, weil das Verschachteln eine Rolle Spielt.

ich habe auch wie dein Vorgehen gemacht, aber das Ergebnis war falsch, was für Laufzeit hast du ausgerechnet?

0

Bei (1) wird die erste Schleife natürlich n mal, die zweite n(n+1)/2 mal durchlaufen. j sollte wohl zu Beginn initialisiert werden, ansonsten ist das Ergebnis nicht definiert.

0

Laufzeit: Man misst vor und nach der interessierenden Stelle die Zeit, was sonst.

Deine Beispiele. Sehr merkwürdig. Wieso initialisierst du im ersten Fall nicht die Variablen aber arbeitest mit ihnen? Was sollen das jj und nn im dritten Fall? So unformatiert ist der Code zu unübersichtlich.

Die Laufzeit in Abha ̈ngigkeit von

n :

    a)  int i, j, k = 0;

    for(k = 1; k <= n; k++) {

    j = j+k;

    } // hier sind die beiden Schleifen nicht verschachtelt

    for(i = j; i >= 1; i--) { 

    print(i+j-k);


    }

b)

for (int i = 1; i <= n; i = i*2) {

       for(int j = n; j <= 9*n; j = j*2) {


            print(j-i);

}

}

c)

 

for(int j = 1; j*j <= n*n; j++) {

      for(int i = 1; i*i <= n; i++) {

           for(int k = 1; k <= i; k++) {
                print(j);

}
}

}

0
@Ackermannn

Die sind Klausuraufgaben,  ich habe hier neu ausgedruckt, könntest Du mir vllt dein Vorgehen zeigen?

0
@Ackermannn

Wie, vorgehen, einfach Zeit nehmen, das ist kein weiteres vorgehen und die unitialisierten Variablen, von denen gelesen wird, sind Angängerfehler und keinesfalls Klausuraufgaben.

0
@priesterlein

Liesen Sie mal bitte das Code nochmal, die Variablen sind doch initialisiert !

wenn es für Sie trivial sind, dann sagen Sie mir was für Laufzeit haben die denn? 

0
@Ackermannn

Junge, je nach CPU ist die Laufzeit anders und OHNE MESSUNG KANN MAN NICHTS SAGEN. MISS DIE ZEIT!

0
@priesterlein

ich spreche nur über das Code, andere Faktoren wie CPU, Speicher , Hardware werden i.A komplett ignoriert. ich glaube meine Frage war, wie man die Zeit von Code misst? 

0

Hey, bleib ruhig. Das sind Übungsaufgaben in Komplexitätstheorie.

1

@priesterlein ich fühle mit dir :'D

0

er will doch unbedingt ne zeitangabe und dann noch ohne angabe der Hardware.. hau einfach nen random value raus. irgendne hardware auf dieser welt wird schon die zeit brauchen die wir uns hier aus den fingern ziehen. ich fange mal an. ich sage 1sekunde

0

Mach es, wie Du es gelernt hast: Invarianten formulieren und die dann beweisen. Das ist etwas länglich, aber mach es halt. Und unterhalte Dich mit Deinen Kommilitonen.

Was möchtest Du wissen?