✔ Laufzeitkomplexizät

[-lion-]

Hallo,

Ich muss eine Formel für die Laufzeitberechnung eines Algorithmus (wandelt binär Zahlen in Integer Zahlen um) entwickeln.
Die Berechnung beinhaltet einzelne Operationen (Wertzuweisung, Vergleich, Indizierung, Addition/Subtraktion, Multiplikation, Prozeduraufruf).

Wie fange ich am besten an? Gesamtlaufzeit (long runningTime = new Date().getTime() - start berechnen? Aber wie komme ich auf die einzelnen Werte?

Hoffe irgendwer von euch kann mir helfen

 

[sheel]

Hi und Willkommen bei tutorials.de,

solls eine Zeitmessung oder Komplexitätsberechnung sein?

Mit Date usw. bekommst du am Schluss, wie lang das Ganze zeitlich gedauert hat,
in Sekunden bzw. Millisekunden. Mehr nicht.
(Außerdem gibts genauere Sachen als Date).

Da du von "Komplexität" redest und Wertzuweisung/Vergleich... unterscheidest
ist deine Aufgabe vermutlich eher, die Anzahl dieser Sachen zu ermitteln,
abhängig von der Zahl, die umgewandelt werden soll

Also etwas wie "Wenn meine Binärzahl n Binärstellen lang ist
braucht die Umwandlung (3*n)+1 Vergleiche, n^2 (hoch 2) Zuweisungen,
unabhängig von der Länge immer 4 Multiplikationen..." usw.
(die Werte sind frei erfunden, nur als Beispiel).

Und aus den genauen Werten kommt man dann, bei Bedarf,
auch zu den Komplexitätsklassen, wie O, O(n^2) ...

Um diese Sachen rauszufinden hilft kein Ausführen/Zeitmessen vom Code,
sondern den Code anschauen und "händisch" zählen/überlegen.
"Wenn die Zahl n Stellen lang ist, geht die Schleife 2n mal durch
und macht bei jedem Durchgang 3 Zuweisungen, 1 Multiplikation..."

Wenn du den Code zeigst können wir dir dabei helfen.

 

[-lion-]

Danke für die schnelle Antwort

Von dieser Funktion muss ich die Laufzeit (Komplexitätsberechnung) berechnen:

public int intOf(String binary){
	int result = 0, i = 0;
	String[] bin = binary.split("");
	while(i < bin.length){
		result *= 2;
		if(bin[i].equals("1")){
		    result++;
			}
			i++;
		}
		return result;
	}

Ich versteh nicht ganz wie und was ich machen soll... Leider weiß ich auch nicht nach was ich genau googeln soll ^^

 

[sheel]

Du brauchst also Wertzuweisung, Vergleich, Indizierung, Addition/Subtraktion, Multiplikation, Prozeduraufruf.

Der Parameter binary, also der String mit der Binärzahl, hat ja eine bestimmte Länge
=
Stellenanzahl der Binärzahl
0101 wären 4 Stellen, 111 nur 3. Ganz normale Stellenanzahl.

Je nach Länge braucht der Code verschieden viele Zuweisungen etc.
Man soll jetzt eine allgemeine Formel zur Berechnung der Zuweisungsanzahl etc.angeben.
Da man beim "Allgemein" die Länge der Binärzahl ja noch nicht weiß,
sagen wir einfach, wir haben eine n-stellige Binärzahl.
(Die Formel muss dann für jede Länge gelten, die man dann eben für n einsetzt)

Um einfach mal mt Indizierung anzufangen:
Wie oft wird auf ein Arrayelement bla[blub] mit diesen eckigen Klammern zugegriffen?
Codezeile 1: Ist ja nur der Funktionskopf, der tut nichts.
Zeile 2: Keine Indexzugriff
Zeile 3: nop, auch nicht (Das [] ist hier nur zur Kennzeichnung, dass das ein Array ist.
Ein tatsächlicher Elementzugriff findet nicht statt)

Zeile 4 ist jetzt eine Schleife.
Wenn man etwas raufschaut, i=0
Bis i<binary.length
Also geht die Schleife so oft durch, wie die Binärzahl Stellen hat (wäre math. gesehen das n)

Zeile 5 wird daher nicht einmal, sondern n-mal ausgeführt, bei einer n-stelligen Binärzahl.
Allerdings ist auch kein Indexzugriff in Zeile 5, daher egal für uns.

Zeile 6 hat jetzt aber einen. Erster Indexzugriff gefunden
Da Z6 auch noch in der Schleife ist, ists nicht einer, sondern n Stück

...auf die Weise weiter bis zum Ende (kein weiterer Indexzugriff).
Insgesamt wurden also n Zugriffe gefunden, bei einer n-stelligen Binäzahl.
Das wärs, für den Indexteil.


Prozeduraufruf:
Man hat einen in Zeile 3. =1 Aufruf
Dann noch einen in Zeile 6, der allerdings in der Schleife ist, die n-mal durchgeht. =n Aufrufe
Insgesamt gibts also n+1 Prozeduraufrufe.


Multiplikation überlass ich jetzt dir
Zum Rest schreib ich dann noch was, ist etwas komplizierter
(eigentlich nicht, aber man übersieht nur leicht was)

 

[-lion-]

Danke jetzt wird mir einiges klarer!

Zur Kontrolle:
Vergleich = n * 2, weil ein Vergleich in Z6 und in Z4 stattfindet und das Ganze passiert dann n mal.
Wertzuweisung = Z2 und Z3 --> 2 mal
Multiplikation = wird einmal in z5 gemacht --> n
Addition = Z9 und Z7(so oft wie 1 vorhanden sind --> schleife die Einser zählt) --> n + gezählt 1

 

[sheel]

Vergleich: Richtig
Multiplikation: Richtig
Subtraktion: Keine drin, also nicht hinschreiben auch richtig


Zuweisung:
Zeile 2: Sind gleich zwei Stück auf einmal =2

Z3: Eine dazu, stimmt = 3

Z5: Das ist eines der Problemsachen, über die ich noch schreiben wollte
result *= 2;
result = result * 2;
...
Merkst?
Dass da eine Multiplikation ist hast du richtig erkannt.
Aber auch eine Zuweisung
n Stück dazu = n+3

Z7: Wie du bei der Addition schon erkannt hast, für jeden Einser in der Binärzahl einmal
Kann man nicht so wirklich in eine math. Formel schreiben, also mit Worten
x++ ist genaugenommen eben auch x=x+1
(man hat ja nur Zuweisung/Addition zur Auswahl, "Inkrementieren" gibts nicht in deiner Aufgabe)
Also n+3 von oben und einmal pro Einser in der Zahl noch dazu

Und Z9. Wieder n Stück

Macht gesamt 2n+3 + Einseranzahl
Min. 2n+3, Max. 3n+3

Addition:
Wieder richtig.
n + Einseranzahl
Min. n, Max. 2n