laufzeitanalyse bestimmen?!

[schooldrivaaa]

nabend,

hab morgen algorithmen und datenstrukturen klausur, aber das besagte thema check ich noch nicht ganz.

folgendes codestück:

for(i=0;i<N;i++)
-----for(j=0;j<N;j++)
-------a[j] = 1;
for(i=0;i<N;i++)
-------a =0;

das ergebnis weiß ich: 3n²+7n+4

ich habe auch einzelne schritte vor mir liegen, aber ich würde selber nich draufkommen.

man zählt zb in der ersten zeile das "i=0" als 1 schritt und das "i<N" als (n+1)

das "i<N" wird angeblich mehrfach abgefragt deshalb ist es mehr als 1 schritt, aber warum, woran sehe ich das, dass es "n-schritte" sind und nicht nur 1?

PLS HELP

THX!

PS die striche sollen nur die tabstobs sein um die eingerückt wurde!

 

[masterchorch]

es sieht auf den ersten blick so aus als würde diese Doppelschleife einen 2 Dimensionalen Array mit Werten füllen.

for(i=0;i<N;i++) <- Ausganswert i=0 ; "tue" solange i<N ; i=i+1 (i wird also mit jedem durchlauf um 1 größer)

-----for(j=0;j<N;j++) <- analog zu 1.

-------a[j] = 1; <- schreibt in die Variable des 2 Dim. Arrays den Wert 1

for(i=0;i<N;i++) <- analog zu 1.

-------a =0; <- schreibt in die Variable des 2 Dim. Arrays den Wert 0

das ganze mal konkret durchgerechnet,
sieh mir evtl. Fehler nach, der Quelltext ist leider nicht vollständig.


for(i=0;i<N;i++)
-----for(j=0;j<N;j++)
-------a[j] = 1;
for(i=0;i<N;i++)
-------a =0;

Ausgangssituation: i=0, j=0, Array leer, N=4 (fiktiv)
1. durchlauf, Schleife 1: i=0, j<N (JA) -> a[0][0] = 1
1. durchlauf, Schleife 2: j=0, j<N (JA) -> a[0][0] = 1
2. durchlauf, Schleife 2: j=1, j<N (JA) -> a[0][1] = 1
3. durchlauf, Schleife 2: j=2, j<N (JA) -> a[0][2] = 1
4. durchlauf, Schleife 2: j=3, j<N (JA) -> a[0][3] = 1
5. durchlauf, Schleife 2: j=4, j<N (NEIN) -> Abbruch Schleife 2
2. durchlauf, Schleife 1: i=1, j<N (JA) -> a[1][4] = 1
1. durchlauf, Schleife 2: j=0, j<N (JA) -> a[1][0] = 1
2. durchlauf, Schleife 2: j=1, j<N (JA) -> a[1][1] = 1

.
.
.

1. durchlauf, Schleife 3: i=0, j<N (JA) -> a[0][0] = 0
2. durchlauf, Schleife 3: i=1, j<N (JA) -> a[1][1] = 0
3. durchlauf, Schleife 3: i=2, j<N (JA) -> a[2][2] = 0
4. durchlauf, Schleife 3: i=3, j<N (JA) -> a[3][3] = 0
5. durchlauf, Schleife 3: i=4, j<N (NEIN) -> Abbruch weil i=N


Wenn du noch garkeine Ahnung hast wie eine Schleife funktioniert
solltest du dir für das Grundverständis erstmal eine simple, nicht verschachtelte Schleife angucken..
Ich schätze mal ihr programiert in Java?

Bsp:

for (int i=0;i<endkriterium;i++) // Fange an bei i=0, tue solange wie i kleiner ist als das endkriterium, vergrößere i jede runde um 1
{
System.out.println("i= "+i);
}

Wenn dein Endkriterum zB. 5 ist, hättest du auf den Bildschirm jetzt exakt folgende Ausgabe:

i= 0
i= 1
i= 2
i= 3
i= 4

 

[ag3nt]

Also Laufzeitanalyse mit so exakten Ergebnissen kenne ich jetzt nicht, aber analog ist es in etwa gleiche

c1:	for(i=0;i<N;i++)
c2:		for(j=0;j<N;j++)
c3:			a[i][j] = 1;

c4: for(i=0;i<N;i++)
c5:		a[i][i] =0;

Zuerst zur Schleife, diese geht zwar über n Werte, danach wird aber noch einmal verglichen,
da der nte Vergleich ja noch glückte, aber erst der n+1te scheitert.

c1 wird als (n+1) mal durchlaufen, der Schleifenkörper jedoch nur n mal. So kannt du dann schon mal folgende
Gleichung aufstellen:

c1*(n+1) +
c2*(n+1)*2 +
c3*(n*n)+
c4*(n+1)+
c5*n

Umgestellt bekommst du dann folgendes:

c1 + c4 + n(c1+c2+c4+c5) + n²(c2+c3)

Jetzt kann man das ganze natürlich noch verfeinern und folgendes annehmen:
Die Zeilen c3 und c5 bestehen nur aus einem Befehl und bekommen den Wert 1.

c3=c5=1

In deinem Fall zur Lösung wurde die Werte für c1, c2 und c4 wohl mit 2 interpretiert, da die for-Schleife
im wesentlichen aus einem Vergleich und einer Werterhöhung besteht.

c1=c2=c4=2

Eingesetzt erhälst du dann:

2+2+n(2+2+2+1)+n²(2+1) = 3n²+7n+4

 

[andr_gin]

Das einzige, was man sicher sagen kann ist, dass der Aufwand ca. quadratisch mit N steigt, aber das ist schon alles.

In der Realität wird dir der Compiler schon eine Menge weg optimieren z.B. die Überprüfung i<n. Weiters wird je nach CPU Architektur nicht ein Befehl nacheinander ausgeführt werden, sondern gleich mehrere auf einmal. Wenn es sich um so simple Operationen wie diese hier handelt, so wird nur schreibend auf den Cache zugegriffen. Bei größeren Datenmengen, wo die Laufzeit erst richtig messbar ist, kann man sagen, dass hier fast nur die Bandbreite des RAMs limitiert.
Die zweite Schleife fällt mit größeren Datenmengen um die 1 Mio. Elemente sowieso nicht mehr ins Gewicht.

Die gesamte Laufzeit in n² und n aufzulösen ist der reinste Schwachsinn (sorry ist aber so). Das hat vielleicht vor 30 Jahren mit kleinen Mikrocontrollern gegolten, aber sicher nicht im heuten Rechnerbereich und mit Java ist das ganze noch viel sinnloser, da man das nie im Leben für Programme einsetzen würde, die sehr CPU lastig sind (was übrigens nur sehr selten der Fall ist).

 

[Daddes]

andr_gin es ging ja nur um eine Übung. Da lohnt es sich nicht sich Gedanken zu machen über den Code selbst. Und schon gar nicht auf HW Ebene. Wundert mich dass du nicht mit Branch Mispredictions kommst

Und keine Ahnung wie du auf die Idee kommst man würde Java nicht einsetzen wenn ein Programm "CPU lastig" ist.