Aufwandsklasse und Laufzeitkomplexität

Question

Code:

public int max(int[] values) {
  int maximum = values[0];
  for (int value : values) {
    if (value > maximum) {
      maximum = value;
    }
  }
  return maximum;
}

public int[][] transpose(int[][] matrix) {
  for (int y = 0; y < matrix.length; ++y) {
    for (int x = 0; x < y; ++x) {
      int temp = matrix[x][y];
      matrix[y][x] = temp;
    }
  }
  return matrix;
}

Bestimmt jeweils die Aufwandsklasse für die Laufzeitkomplexität beider Methoden. Rechnet und begründet ausführlich. Geht davon aus, dass alle Operatoren und die return-Anweisung die Komplexität O(1) haben.

Answer 1

Die obere Methode dauert ja in Abhängigkeit von der Anzahl n der Elemente im Array. Somit ist die Laufzeitklasse O(n)

Die untere hat eine verschachtelte for-Schleife. Sie braucht also in Abhängigkeit von 2 Parametern n und m genau n×m Durchläufe. Man spricht hier vereinfacht gesagt dann von O(n²).

Beste Grüße

Felix