# Laufzeitanalyse 2 for-Schleifen



## adp4sure (7. Aug 2012)

Hi,

gegeben ist folgender Code:


```
public static int[] averageRGB(BufferedImage img) {
		int[] averageRGBValues = new int[3];
		int height = img.getHeight();
		int width = img.getWidth();
		int sumRed = 0;
		int sumGreen = 0;
		int sumBlue = 0;
		for(int x = 0; x < width; x++) {
			for(int y = 0; y < height; y++) {
				int rgb = img.getRGB(x, y);
				Color c = new Color(rgb);
				sumRed = sumRed + c.getRed();
				sumGreen = sumGreen + c.getGreen();
				sumBlue = sumBlue + c.getBlue();
			}
		}
		int pixels = height * width;
		averageRGBValues[0] = sumRed / pixels;
		averageRGBValues[1] = sumGreen / pixels;
		averageRGBValues[2] = sumBlue / pixels;
		return averageRGBValues;
	}
```

Nun soll die Laufzeit dieser Methode exakt angegeben werden. Jeder Methodenaufruf hat dabei eine Laufzeit von 1 und das Bild ist _n_ Pixel breit und hoch. 

Mein Versuch, indem ich die Laufzeit immer reingeschrieben habe:


```
public static int[] averageRGB(BufferedImage img) {
		int[] averageRGBValues = new int[3];  // 1
		int height = img.getHeight();  //1
		int width = img.getWidth();    //1
		int sumRed = 0;                //1
		int sumGreen = 0;              //1
		int sumBlue = 0;               //1
		for(int x = 0; x < width; x++) {   //1   1   n   n
			for(int y = 0; y < height; y++) {  // 1   1   n   n
				int rgb = img.getRGB(x, y);   // 1
				Color c = new Color(rgb);     // 1
				sumRed = sumRed + c.getRed(); // 1
				sumGreen = sumGreen + c.getGreen(); // 1
				sumBlue = sumBlue + c.getBlue();  // 1
			}
		}
		int pixels = height * width;   //1
		averageRGBValues[0] = sumRed / pixels;   //1
		averageRGBValues[1] = sumGreen / pixels; //1
		averageRGBValues[2] = sumBlue / pixels; //1
		return averageRGBValues; //1
	}
```

Somit komme ich auf T(n) = 13 + 4n + 7n²

Aber in der nächsten Teilaufgabe steht, falls man die Laufzeitanalyse nicht lösen konnte, so soll man von T(n)= 9 + 12n + 0,5n² ausgehen, was sich ja gar nicht meiner Analyse deckt.

Kann mir jemand helfen, wo ich falsch liege?


----------



## tribalup (7. Aug 2012)

Also es ist wirklich schwer zu verstehen was eigentlIch die aufgabe ist.
Die methode wird nur 1 mal aufgerufen. Wenn du hier Hilfe willst, dann solltest du die Aufgabe besser formulieren.
We du auf dein Ergebnis kommst ist mir auch nicht klar.


----------



## adp4sure (7. Aug 2012)

Aufgabenstellung im *Wortlaut*:
*Ermitteln Sie die Laufzeit T(n), die die Funktion benötigt. Das Bild ist n Pixel breit und hoch. Gehen Sie davon aus, dass jeder Methodenaufruf eine Laufzeit von 1 hat. Dokumentieren Sie ihr Vorgehen mit Hilfe der Zeilennummern.*

Und nun ist mir nicht klar, was du meinst. Ich erkläre kurz, wie ich auf mein Ergebnis komme:


```
int[] averageRGBValues = new int[3];
        int height = img.getHeight();
        int width = img.getWidth();
        int sumRed = 0;
        int sumGreen = 0;
        int sumBlue = 0;
```

Das sind sechs Anweisungen, also 6.


```
int pixels = height * width;
        averageRGBValues[0] = sumRed / pixels;
        averageRGBValues[1] = sumGreen / pixels;
        averageRGBValues[2] = sumBlue / pixels;
        return averageRGBValues;
```

Das sind 5 Anweisungen, also 5.


```
for(int x = 0; x < width; x++) {
            for(int y = 0; y < height; y++) {
                int rgb = img.getRGB(x, y);
                Color c = new Color(rgb);
                sumRed = sumRed + c.getRed();
                sumGreen = sumGreen + c.getGreen();
                sumBlue = sumBlue + c.getBlue();
            }
        }
```

In der for-Schleife 
	
	
	
	





```
int x = 0
```
 und 
	
	
	
	





```
x < width
```
 ergeben 2 Anweisungen. Somit komme ich auf 13.
In der for-Schleife ergibt 
	
	
	
	





```
x++
```
 und 
	
	
	
	





```
x < width, int y = 0
```
 und 
	
	
	
	





```
y < height
```
 ergeben 4n-Anweisungen.
In der zweiten for-Schleife ergibt 
	
	
	
	





```
y++
```
 und 
	
	
	
	





```
y < heigth
```
 plus alles was in der zweiten for-Schleife drin ist, insgesamt 7n²-Anweisungen. 

Stimmt das?


----------



## tribalup (7. Aug 2012)

Also was mir auf die Schnelle auffällt ist, dass die 0.5n² zu einem gebrochenen Ergebnis führen kann und somit wahrscheinlich nicht korrekt ist. Ich schau grad mal drüber.


----------

