Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
--- Praktische Informatik (http://www.informatikerboard.de/board/board.php?boardid=6)
---- Algorithmen (http://www.informatikerboard.de/board/board.php?boardid=17)
----- ELOPs zählen. (http://www.informatikerboard.de/board/thread.php?threadid=2822)

Geschrieben von Nunzio am 29.01.2016 um 17:40:

  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)?


Geschrieben von eulerscheZahl am 29.01.2016 um 18:30:

 

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.


Geschrieben von Nunzio am 29.01.2016 um 18:38:

 

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.


Geschrieben von eulerscheZahl am 29.01.2016 um 18:53:

 

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
}


Geschrieben von Nunzio am 29.01.2016 um 19:00:

 

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?


Geschrieben von eulerscheZahl am 29.01.2016 um 19:02:

 

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


Geschrieben von Nunzio am 29.01.2016 um 19:20:

 

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?


Geschrieben von eulerscheZahl am 29.01.2016 um 19:24:

 

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.


Geschrieben von Nunzio am 29.01.2016 um 19:31:

 

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?


Geschrieben von eulerscheZahl am 29.01.2016 um 19:55:

 

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.


Geschrieben von Nunzio am 29.01.2016 um 20:09:

 

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?


Geschrieben von eulerscheZahl am 29.01.2016 um 20:12:

 

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


Forensoftware: Burning Board, entwickelt von WoltLab GmbH