ELOPs zählen.

29.01.2016, 17:40

Nunzio

ELOPs zählen.

Hey,

Ich will in einigen Algorithmen die maximalen ELOPS zählen. Hab dafür folgende Aufgabe

Der Algorithmus berechnet die Dualdarstellung einer Dezimalzahl

Eingabe : Positive Zahl x
n:= 1; // 1 ELOP
h:= x; // 1 ELOP
while (h>1) { // n + 1 ELOP (Die Schleife wird ja n mal durchlaufen, also n Abfragen + 1, da die letzte Abfrage ja mit falsch beantwortet wird und es dann weitergeht.
h := h/2; // 2n ELOPS
n := n+1 // 2n ELOPS
}
while (n > 0) { // n + 1 ELOP
yn := x%2; // 2n ELOPS
x := x/2; // 2n ELOPS
n := n-1; // 2n ELOPS
}
Ausgabe : y1, y2,....., yn.

Also 12n + 4 ELOPS. Ist das richtig? Und wie schreibe ich das dann auf also ala Tmax (A,x)?

29.01.2016, 18:30

Auf diesen Beitrag antworten »

eulerscheZahl

n ist für die erste Schleife vielleicht nicht ganz glücklich gewählt, da n ja zu Beginn 1 ist.
Es sind x-1 Durchläufe und x Abfragen (da liegst du um 1 daneben).
Danach ist n=x, weshalb du x Durchläufe der 2. Schleife hast.

29.01.2016, 18:38

Auf diesen Beitrag antworten »

Nunzio

Hey, danke für deine Antwort.

Könntest du vielleicht meinen Text kopieren und dort die ELOPS ändern? Ich kann nicht verstehen, was du wo änderst.

Liebe Grüße

n muss nehmen, weil das so vorgegeben ist bei mir.

29.01.2016, 18:53

Auf diesen Beitrag antworten »

eulerscheZahl

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:

n:= 1; // 1 ELOP
h:= x; // 1 ELOP
while (h>1) { // x ELOP (Die Schleife wird x-1 mal durchlaufen, also x Abfragen - einfach mal mit kleiner Zahl ausprobieren)
h := h/2; // 2(x-1) ELOPS
n := n+1 // 2(x-1) ELOPS
}
//jetzt ist n==x
while (n > 0) { // x + 1 ELOP
yn := x%2; // xn ELOPS
x := x/2; // xn ELOPS
n := n-1; // xn ELOPS
}

29.01.2016, 19:00

Auf diesen Beitrag antworten »

Nunzio

Wieso denn xn? Wir haben in der Uni vergleichbare Sachen mit Elops durchgezählt, aber niemals wurden 2 Buchstaben verwendet :/ Jetzt bin ich verwirrt. Was kommt denn dann als Ergebnis raus?

29.01.2016, 19:02

Auf diesen Beitrag antworten »

eulerscheZahl

Ups, ich wollte das n ersetzen, nicht die 2.

29.01.2016, 19:20

Auf diesen Beitrag antworten »

Nunzio

Also jetzt versteh ich wirklich überhaupt nichts mehr. Kann es sein, das dieses Thema überall anders gelehrt wird? In vielen Skripten die ich mir online rausgesucht habe, steht was anderes :/ Also ist die Zeitkomplexität einfach die Anzahl ELOPS?

29.01.2016, 19:24

Auf diesen Beitrag antworten »

eulerscheZahl

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:

n:= 1; // 1 ELOP
h:= x; // 1 ELOP
while (h>1) { // x ELOP (Die Schleife wird x-1 mal durchlaufen, also x Abfragen - einfach mal mit kleiner Zahl ausprobieren)
h := h/2; // 2(x-1) ELOPS
n := n+1 // 2(x-1) ELOPS
}
//jetzt ist n==x
while (n > 0) { // x + 1 ELOP
yn := x%2; // 2x ELOPS
x := x/2; // 2x ELOPS
n := n-1; // 2x ELOPS
}

So wollte ich das eigentlich schreiben.

Bei Eingabe x gibt es 12x-1 Elementaroperationen.
Bei der Zeitkomplexität kommt es darauf an, ob die die genaue Zeit haben willst, oder nur die O-Notation.

29.01.2016, 19:31

Auf diesen Beitrag antworten »

Nunzio

Wieso wird die erste while Schleife x mal ausgeführt und die 2. x+1? Ich kann mir das überhaupt nicht vorstellen. Also ich habe gedacht, dass die while Schleife x mal durchläuft und beim letzten versuch zwar prüft, aber nicht durchläuft. Wieso ist das in der zweiten so, aber in der ersten nicht?

29.01.2016, 19:55

Auf diesen Beitrag antworten »

eulerscheZahl

Ich sollte nicht Handball schauen und nebenher hier schreiben unglücklich

code:
1: 2:	while (h>1) { h := h/2;

Da wird h jedes mal halbiert, also gibt es nur log2(h) viele Durchläufe.
Deshalb ist auch n nur log2(h), also wird auch die 2. Schleife nicht öfter durchlaufen.

29.01.2016, 20:09

Auf diesen Beitrag antworten »

Nunzio

Zitat:

Original von eulerscheZahl
Ich sollte nicht Handball schauen und nebenher hier schreiben unglücklich

Tut mir leid, ich bin einfach schwer von Begriff. unglücklich

Okay, das leuchtet ein, hast du vielleicht eine kleine Übungsaufgabe für mich?

29.01.2016, 20:12

Auf diesen Beitrag antworten »

eulerscheZahl

Kannst dir ja mal die Laufzeit der binären Suche anschauen, die ist auch logarithmisch.

Neue Frage »

Antworten »

ELOPs zählen.

Verwandte Themen