ELOPs zählen. |
29.01.2016, 17:40 | Auf diesen Beitrag antworten » | |||||
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 |
|
|||||
Anzeige | ||||||
|
||||||
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 |
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
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 |
Tut mir leid, ich bin einfach schwer von Begriff. 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. |
|