Laufzeitanalyse 2 for-Schleifen

A

adp4sure

Gast
Hi,

gegeben ist folgender Code:

Java:
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:

Java:
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

Bekanntes Mitglied
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.
 
A

adp4sure

Gast
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:

Java:
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.

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

Das sind 5 Anweisungen, also 5.

Java:
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
Code:
int x = 0
und
Code:
x < width
ergeben 2 Anweisungen. Somit komme ich auf 13.
In der for-Schleife ergibt
Code:
x++
und
Code:
x < width, int y = 0
und
Code:
y < height
ergeben 4n-Anweisungen.
In der zweiten for-Schleife ergibt
Code:
y++
und
Code:
y < heigth
plus alles was in der zweiten for-Schleife drin ist, insgesamt 7n²-Anweisungen.

Stimmt das?
 

tribalup

Bekanntes Mitglied
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.
 

Neue Themen


Oben