Komplexität

[MKI]

Hi,
Ich(oder wir, da es eine Gruppenarbeit ist) habe ein kleines Problem bei einer Abgabe für die HS.

Und zwar habe ich folgende Methoden:

-Arrays 2D:

private static boolean istVorhanden(int[][] data, int z) {
		if (data == null || data.length == 0)
			return false;

		for (int j = 0; j < data.length; j++) {
			while (data[j] == null || data[j].length == 0) {
				j++;
				if (j == data.length)
					return false;
			}

			for (int i = 0; i < data[j].length; i++) {
				if (data[j][i] == z)
					return true;
			}
		}
		return false;
	}

-Arrays 3D:

private static int getAnzahl(int [][][] data, int z){  	
		if (data==null) return 0;
		if (data.length==0) return 0; 
		
		
		int i=0, j=0, k=0;  //schleifenvariable
		int a1=0;
		
		while (k < data.length) {
			if (data[k]==null) k++;
			if (data[k].length==0) k++; 
			
			while (j < data[k].length) {
				if (data[k][j]==null) j++;
				if (data[k][j].length==0) j++; 
				
				while (i < data[k][j].length) {
					if (data[k][j][i] == z)
						a1++;
					i++;
				}
				j++;
				i = 0;
			}
			k++;
			j = 0;
		}
	
	return a1;
	}

Array 2D überprüft ob ein Wert ("z") in einem Array vorhanden ist.
Array 3D überprüft wie oft ein Wert ("z") im Array vorhanden ist.

Jetzt wurde wir gefragt welche Komplexität jede dieser Methoden besitzt.
Bei Array 2D haben wir als Komplexität 0(1) als best-case Szenario angegeben.
Dies war laut dem Prof falsch. Was würdet ihr zu Komplexität sagen oder wie würdet ihr sie berechnen?
Ausserdem meinte er, wir sollten die Komplexität verringern. Wie? (Die Fehlerbehebung ist absichtlich)

Bei Array 3D wurden wir, nun vollends verwirrt, wieder nach der Komplexität im best-case Szenario gefragt. Auch hier waren unsere Antworten falsch.

Leider konnten uns die Tutoren auch nicht weiterhelfen...

Ich/wir würden uns sehr über eine Antwort freuen. Vermutlich sind wir hier noch öfters zu Gast

Gruß, MKI

 

[nillehammer]

Es gibt sehr viele Arten, Komplexität zu messen. Ohne Kontext kann die Frage also nicht beantwortet werden. Allerdings glaube ich hier ganz stark, dass Euer Prof. die zyklomatische Komplexität Eures Codes meinte. Die genaue Rechenformel kenne ich dafür nicht. Aber grob lässt sich sagen, dass diese steigt, je mehr verschachtelte Verzweigungen im Code sind. Da Ihr hier einmal dreifach und einmal vierfach verschachtelt, würde ich anehmen, dass die Komplexität recht hoch ist. Ich selbst programmiere fast komplett ohne Verschachtelungen und wenn dann höchstens doppelt verschachtelt (ein if innerhalb einer Schleife ist schonmal drinnen). Alles darüber hinaus ist für Menschen schwer lesbar und der Programmablauf noch schwerer nachvollziehbar.

 

[hüteüberhüte]

Ganz einfach: Zwei geschachtelte Schleifen n^2, drei geschachtelte Schleifen n^3. (Wenn alle Arrays die Länge n haben.)

Über best case kann man sich streiten, weil zuerst alle null- und leeren Arrays "übersprungen" werden

 

[nillehammer]

Ausserdem meinte er, wir sollten die Komplexität verringern. Wie? (Die Fehlerbehebung ist absichtlich)

Mit Euren verschachtelten Schleifen- und If-Konstrukten wollt ihr eine bestimmte Aufgabe erfüllen. Versucht fachlich die Aufgabe in Teilaufgaben zu zerlegen (bei einem 2D-Array z.B. iterateLines, iterateColumns). Teilt diese Teilaugaben in Methoden mit geeigneten Parametern und return-Werten auf. Dann liest sich der Code fast wie eine Geschichte.

Zum Beispiel der Code hier

            if (data[k]==null) k++;
            if (data[k].length==0) k++;

Hier werden offensichtlich Bedingungen abgefragt, die dazu führen, dass ein Element übersprungen wird. Abgesehen davon, dass man die beiden ifs auch mit einem || zusammenfassen könnte, macht daraus doch ne schöne Methode mit sprechendem Namen:

private static boolean mustSkip(int[] intArr) {
  return intArr == null || intArr.length == 0;
}

// Oder auch so:
private static int incrementIfArrayEmpty(int intToIncrement, int[] intArrToCheck) {

   if(intArrToCheck == null || intArrToCheck.length == 0) {
      return intToIncrement++;
   }

   return intToIncrement;
}

// Benutzung dann
k = incrementIfArrayEmpty(k,data[k]);

Ist sicher nicht perfekt und vielleicht hab ich den Sinn Eures Codes auch nicht ganz verstanden, aber die Idee dürfte klar sein.

 

[hüteüberhüte]

Hätte es vielleicht so geschrieben (habe keine extra Methode für mustSkip):

    public static <T> int treffer(T[][] array, T suche) {
        if (array == null || suche == null) {
            throw new IllegalArgumentException();
        }
        int c = 0;
        for (T[] ts : array) {
            if (ts == null) {
                continue;
            }
            for (T t : ts) {
                if (suche.equals(t)) {
                    c++;
                }
            }
        }
        return c;
    }
    
    public static <T> int treffer(T[][][] array, T suche) {
        if (array == null || suche == null) {
            throw new IllegalArgumentException();
        }
        int c = 0;
        for (T[][] tses : array) {
            if (tses == null) {
                continue;
            }
            for (T[] ts : tses) {
                if (ts == null) {
                    continue;
                }
                for (T t : ts) {
                    if (suche.equals(t)) {
                        c++;
                    }
                }
            }
        }
        return c;
    }
    
    public static void main(String[] args) {
        System.out.println(treffer(new Integer[][]{null, {null, 1, 0, 1, null}, null, {null, 1, 0, 1, null}, null}, 1));
        System.out.println(treffer(new Integer[][][]{null, {null, {null, 1, 0, 1, null}, null}, null, {null, {null, 1, 0, 1, null}, null}, null}, 1));
    }

Vielleicht etwas übersichtlicher und einfacher zu analysieren. Nachteil: Generische Methode: Funktioniert nicht mit Arrays primitiver Typen.

 

[MKI]

Hi,
Danke erstmal für eure schnellen antworten.
Erstmal zur komplexität des codes an sich:

Da wir erst dieses Semester mit Informatik angefangen haben, sollte sich das ganze auf die dargestellten Möglichkeiten (for, while, erstmal nur die eine Methode usw...) beschränken, mehr hatten wir noch nicht
Gerne nehmen wir auch neues hinzu, wobei allerdings unser Prof uns dann dazu löchern wird, ob wir das alles auch genau verstanden haben, was sicherlich noch nicht so schnell der Fall sein wird

Wegen der Komplexitäts-Angabe:
Nochmal zur Erinnerung : Er hat uns nach dem BEST-CASE gefragt, d.h. wenn das erste Feld des Arrays überprüft wird, und sich dort sofort das gesuchte Element befindet, müsste dies doch der Best-case sein oder? Somit wird 0(n^2) erstmal ausgeschlossen (als best-case).

Es handelt sich übrigens um eine Bewertung nach den Landau Symbolen (Landau-Symbole ? Wikipedia)

Gruß, MKI

 

[langhaar!]

Der Best-Case ergibt sich meines Erachtens, wenn data = null ist.
Dann wird eine von sämtlichen Eingabegrößen unabhängige, also konstante Anzahl von Schritten ausgeführt. Und der liegt definitiv in O(1).

Vielleicht möchte euer Prof. eine schärfere Abschätzung, als Omikron (also O). Ihr könnt den Aufwand auch mit Theta (1) abschätzen.

Der generelle Aufwand ist O(data.length zum Quadrat).

 

[MKI]

So, haben es jetzt nochmal versucht und diesmal hat er auch tatsächlich O(1) bei aufgabe array2d als richtig anerkannt. Die komplexität haben wir nicht groß verändert.
Bei Array 3D war die Komplexität im best und worst-case O(n*m*k), da ja das ganze Array durchsucht wird.
Vielen Dank an alle!

Gruß, MKI

 

[Daassan]

dürfte ich fragen warum im best und im worst case der aufwand n*m*k ist?
denn im best case hast du ein 1*1*1 langes array damit wird es 1 oder sehe ich das falsch
und versessern könnt ihr auf jeden fall in dem ihr davor nochmal in sortierung drüberlaufen lässt dann wir d aus der suche ein o(n*log(n)) bzw O(n*m*log(p))

und nillehammer was gibt es denn noch für komplexitäten? innerhalb von code kenn ich nur die laufzeit also zb. O(n)
bin vor kurzen mit studium fertig geworden aberleider nur ein dumemr bechalor da wurde viel ausgelassen.
vor allem in der theoretischen informatiker die mir eigentlich recht spaß gemacht hatte

danke ;D

 

[hüteüberhüte]

Ehm, wenn n=m=k=1, dann auch n*m*k=1. Nur so nebenbei

Lg

Gesendet mit Tapatalk 2

 

[Daassan]

ja gut ok adnn haben wir sehr große arrays best case wäre dann das erste als treffer
aber ja ... ich seh gerade das hier wird nicht nur nach einem vorhandensein gescahut sondern nach ner anzahl...
dann muss man natürlich alles anschauen ok seh ich ein ^^