Laufzeitanalyse 2 for-Schleifen

[adp4sure]

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]

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]

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]

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.