# Laufzeitfunktionen und Ausführungszeiten



## BoZoM (1. Apr 2010)

hallo an alle,

ich habe vorhin ge googelt und hab dieses forum endeckt muss sagen das der forum hier echt klasse ist. Doch nun hab ich eine aufgabe an der backe die ich nicht lösen konnte. vileicht könntet ihr mir helfen

1. Bestimmen Sie fuer jede der folgenden Laufzeitfunktionen T(n) und Ausfuehrungszeiten
t die jeweils groeßte Laenge n der Eingabedaten, die in der Zeit t verarbeitet werden koennen. Nehmen
Sie hierfuer vereinfachend an, dass der zu Grunde liegende Algorithmus genau T(n) Sekunden braucht,
um das Problem zu loesen. (Einige Angaben sind nur per ”Ausprobieren“ mit Excel loesbar!)

(solte ne Tabelle sein)

t  	              1 sec   	1 min  	1 h  	1 Tag  	1 Monat  	1 Jahr  	1 Jhdt
ln n 	
Wurzel n 	
n 	
n ln n 	
n2 	
n3 	
2n 	
n! 


2. Welche Laufzeit T(n) benoetigt die Multiplikation zweier (n X n)-Matrizen genau? (Verwenden
Sie f¨ur jede Elementaroperation [+, *, =, Vergleich, . . . ] die konstante Laufzeit c0.)
Wie lautet T(n) in der Q-Notation und in der O-Notation?
Begruenden Sie Ihre Antworten kurz.


danke schonmal danke für eure antworten


----------



## Marco13 (1. Apr 2010)

Eigene Ansätze...? :noe:


----------



## BoZoM (1. Apr 2010)

nein leider nicht. sitze die ganze zeit davor kp wie ich das programmieren soll.


----------



## Marco13 (2. Apr 2010)

Eigentlich gibt es da nichts zu programmieren. Oder meinst du die "Ausprobier-Funktionen"?


----------



## BoZoM (2. Apr 2010)

also ich soll dazu ne applikation schreiben. ja glaub das da diese " ausprobier-funktion " reinmus. also mir fält da so ein lösungsweg ein unswar das wenn man die applikation ausführt man einen wert eingibt der und durch die "ausprobier-funktion" erechnet wirt.


----------



## Final_Striker (2. Apr 2010)

n

1 sek -> n <= 1
1 min -> n <= 60
1 std -> n <= 60*60
1 tag -> n <= 60*60*24
...
...

n²

1 sek -> n < 1
1 min -> n < 8  // Wurzel aus 60
1 std -> n <= 60 // Wurzel aus 60*60
1 tag -> n < 294 // Wurzel aus 60*60*24
...
...

Das bedeutet, ein Algorithmus mit T(n²) Laufzeit darf höchstens eine Eingabe der Länge 293 haben, damit er spätestens nach einem Tag fertig ist. ;-)

Edit:

Du musst quasi immer eine Zahl suchen, die für n eingesetzt, eine Laufzeit kleiner z.b 1 min (60 sek), 1 std (3600 sek) usw. ergibt.
Ein Algorithmus mit T(n³) würde mit einer Eingabe der Länge n=10, 1000 Sekunden brauchen um das Ergebnis zu berechnen.


----------



## BoZoM (2. Apr 2010)

hmm wie würde ich das dann in eine applikation einfügen??


----------



## 0x7F800000 (2. Apr 2010)

Imho kann man den letzten eintrag der ersten zeile sowas von knicken... 
Als was will man denn 10^1350829557 vernünftig abspeichern? In long passt's garantiert nicht. In BigInteger passts niemals in keinen superrechner. Selbst recht ungenaue Approximationen kann man nicht abspeichern, weil double auch nur bis ~10^300 geht... Wtf?

Also, da dürfte imho an einigen stellen nur noch schwachsinn rauskommen...


----------



## Final_Striker (2. Apr 2010)

was soll 10^1350829557 sein ???


----------



## 0x7F800000 (2. Apr 2010)

hab ich mich i-wo verrechnet? ???:L
Ein Jahrhundert ist grob geschätzt 100*365*24*60*60 = 3 153 600 000 sekunden.
Wenn jetzt eingabegröße n gesucht ist s.d. ln(n)=3153600000, dann hängt diese größe exponentiell von dieser grässlichen Zahl ab: n = e^3153600000, in zehner-potenz umgerechnet: 
10^(3153600000/ln(10)) = 10^1369591080 (ich hab davor 10^1350829557 geschrieben, hab wohl mit einem etwas kürzeren 360er-bank-jahr gerechnet). Macht keinen großen qualitativen Unterschied, wie man sieht... :bahnhof: In doubles kriegt man das jedenfalls nicht vernünftig ausgerechnet.


----------



## BoZoM (2. Apr 2010)

könnte man das in einem sortierten Array machen.

sprich wen der gesuchte wert 23 ist kann die Hälfte der Elemente von der weiteren Betrachtung ausgeschlossen werden, indem das gesuchte Element mit dem Element verglichen wird, dass sich in der Mitte des Arrays befindet. Das wiederholt man immer so weiter bis man den wert hat.


z.b 

haben wir folgende elemente:

4
7
12
23
45
48
64
65
86

da der gesuchte wert 23 guckt man erst in der helfte der werte. das wäre dann 45 die andere hälfte ist unwichtig da sie größer als der gesuchte wert ist. jetzt bleiben die werte :

4
7
12
23
45

jetzt setzt man wieder an der helfte an dies geht immer so weiter bis man den gesuchten wert hat


----------



## Final_Striker (2. Apr 2010)

und was für werte stehen denn in deinem array ???


----------



## BoZoM (2. Apr 2010)

nichts ich denke mal das man das aus der tabelle entnehmen soll


----------



## Final_Striker (2. Apr 2010)

man kann es sicher auf verschiedene weise lösen, also mach es doch einfach so wie du denkst. ;-)


----------



## BoZoM (2. Apr 2010)

ja die frage ist ob das auch richtig ist. die aufgabe ist wichtig für mich wegen mein testat. ich wollte eure lösungsvorschläge hören


----------



## Final_Striker (2. Apr 2010)

Wie wäre es damit:
DU machst einen Lösungsvorschlag und WIR sagen dir dann, ob der richtig ist oder nicht.


----------



## BoZoM (2. Apr 2010)

ich denke mal ich also soll eine aplikation schreiben. wenn die aplikation ausgeführt wird muss ich mich für einen der Laufzeitfunktionen und Ausführungszeiten entscheiden. dies wird mir dann ausgerechnet zurückgegeben.

und bei der anderen aufgabe hab ich keine ahnung wie ich da ran gehen soll


----------



## Final_Striker (2. Apr 2010)

Also bei der ersten Aufgabe würde ich sagen, dass du nur die Werte ausrechnen sollst um diese Tabelle auszufüllen. Von einer Anwendung schreiben steht da ja nichts, oder?

Zu Aufgabe 2:

Du informierst dich z.B. bei Wikipedia, wie man zwei Matrizen multipliziert. Dann setzt du das in einem Algorithmus um. Durch die 3 Schleifen im Algorithmus stellst du dann fest, dass er eine Laufzeit von O(n³) hat. ;-)


----------



## BoZoM (2. Apr 2010)

wie hast du das rausbekommen


----------



## Final_Striker (2. Apr 2010)

Wir hatten im letzten Semester in der Algorithmen Vorlesung die Matrizen-Multiplikation behandelt.


----------



## BoZoM (2. Apr 2010)

hast du vileicht ne rechnung gemacht damit ich die rechnung nachvollziehen kann.


----------



## 0x7F800000 (2. Apr 2010)

BoZoM hat gesagt.:


> könnte man das in einem sortierten Array machen.
> 
> sprich wen der gesuchte wert 23 ist kann die Hälfte der Elemente von der weiteren Betrachtung ausgeschlossen werden, indem das gesuchte Element mit dem Element verglichen wird, dass sich in der Mitte des Arrays befindet. Das wiederholt man immer so weiter bis man den wert hat.
> 
> ...


Intervallhalbierungsverfahren? gut. :applaus:
Arrays? Blödsinn. :noe:



Final_Striker hat gesagt.:


> Wir hatten im letzten Semester in der Algorithmen Vorlesung die Matrizen-Multiplikation behandelt.



In der Vorlesung über Algorithmen wurde Matrix-Multiplikation behandelt, und man hat da _Strassen nicht mal erwähnt_? Das ist ziemlich schräg, weil es eigentlich so ein Standard-Beispiel für D&Q und Master-Theorem ist... ???:L


----------



## Final_Striker (2. Apr 2010)

0x7F800000 hat gesagt.:


> In der Vorlesung über Algorithmen wurde Matrix-Multiplikation behandelt, und man hat da _Strassen nicht mal erwähnt_? Das ist ziemlich schräg, weil es eigentlich so ein Standard-Beispiel für D&Q und Master-Theorem ist... ???:L



Es ging um Dynamische Programmierung. Ein Teil davon handelte von Matrix-Kettenmultiplikation und dazu braucht man halt einen Algorithmus mit dem man 2 Matrizen multiplizieren kann. ;-)


----------



## 0x7F800000 (3. Apr 2010)

Final_Striker hat gesagt.:


> Es ging um Dynamische Programmierung. Ein Teil davon handelte von Matrix-Kettenmultiplikation und dazu braucht man halt einen Algorithmus mit dem man 2 Matrizen multiplizieren kann. ;-)


Aaah! Auch schön


----------



## BoZoM (3. Apr 2010)

ich habe für aufgabe 2 ne applikation nur ist da ein fehler denn ich nicht lösen konnte könnt ihr mir da weiter helfen. wäre den die applikation richtig??

hier der code:

public class matrizen{

  private double[][] arr;

  public matrizen(int m, int n) {

    arr = new double[m][n];
  }

  public matrizen(Matrix a) {


    int m = a.getColumnDimension();
    int n = a.getRowDimension();
    arr = new double[m][n];

    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        arr_[j] = a.arr[j];
      }
    }
  }

  public int getColumnDimension() {

    return arr.length;
  }

  public int getRowDimension() {

    return arr[0].length;
  }

  public double get(int i, int j) {

    return arr[j];
  }

  public void set(int i, int j, double s) {

    arr[j] = s;
  }

  public static matrizen matmult(matrizen a,  b) {


    int m = a.getColumnDimension();
    int l = a.getRowDimension();
    int n = b.getRowDimension();

    Matrix c = new Matrix(n, m);

    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        c.arr[j] = 0.0;
        for (int k = 0; k < l; k++) {
          c.arr[j] += a.arr[k] * b.arr[k][j];
        }
      }  c = matmult(a, b);
    }

    return c;
  }

  public  Matrix minus(Matrix a) {


    int m = getColumnDimension();
    int n = getRowDimension();
    Matrix c = new Matrix(m, n);

    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        c.arr[j] = arr[j] - a.arr[j];
      }
    }
    return c;
  }

  public  Matrix plus(Matrix a) {


    int m = getColumnDimension();
    int n = getRowDimension();
    Matrix c = new Matrix(m, n);

    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        c.arr[j] = arr[j] + a.arr[j];
      }
    }
    return c;
  }

  public void plusGleich(Matrix a) {


    for (int i = 0; i < getColumnDimension(); i++) {
      for (int j = 0; j < getRowDimension(); j++) {
        arr[j] += a.arr[j];
      }
    }
  }

  public void minusGleich(Matrix a) {


    for (int i = 0; i < getColumnDimension(); i++) {
      for (int j = 0; j < getRowDimension(); j++) {
        arr[j] -= a.arr[j];
      }
    }
  }

  public String toString() {


    String s = "";
    for (int i = 0; i < getColumnDimension(); i++) {
      for (int j = 0; j < getColumnDimension(); j++) {
        s += arr[j] + ", ";
      }
      s += "\n";
    }
    return s;
  }
}_


----------



## hfu (3. Apr 2010)

Wenn du das Ganze in die 
	
	
	
	





```
- Tags schreibst kann man es noch besser lesen ;-)
```


----------



## BoZoM (3. Apr 2010)

aso wuste ich nicht hier nochmal dann:



```
public class matrizen{

private double[][] arr;

public matrizen(int m, int n) {

arr = new double[m][n];
}

public matrizen(Matrix a) {


int m = a.getColumnDimension();
int n = a.getRowDimension();
arr = new double[m][n];

for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
arr[i][j] = a.arr[i][j];
}
}
}

public int getColumnDimension() {

return arr.length;
}

public int getRowDimension() {

return arr[0].length;
}

public double get(int i, int j) {

return arr[i][j];
}

public void set(int i, int j, double s) {

arr[i][j] = s;
}

public static matrizen matmult(matrizen a, b) {


int m = a.getColumnDimension();
int l = a.getRowDimension();
int n = b.getRowDimension();

Matrix c = new Matrix(n, m);

for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
c.arr[i][j] = 0.0;
for (int k = 0; k < l; k++) {
c.arr[i][j] += a.arr[i][k] * b.arr[k][j];
}
} c = matmult(a, b);
}

return c;
}

public Matrix minus(Matrix a) {


int m = getColumnDimension();
int n = getRowDimension();
Matrix c = new Matrix(m, n);

for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
c.arr[i][j] = arr[i][j] - a.arr[i][j];
}
}
return c;
}

public Matrix plus(Matrix a) {


int m = getColumnDimension();
int n = getRowDimension();
Matrix c = new Matrix(m, n);

for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
c.arr[i][j] = arr[i][j] + a.arr[i][j];
}
}
return c;
}

public void plusGleich(Matrix a) {


for (int i = 0; i < getColumnDimension(); i++) {
for (int j = 0; j < getRowDimension(); j++) {
arr[i][j] += a.arr[i][j];
}
}
}

public void minusGleich(Matrix a) {


for (int i = 0; i < getColumnDimension(); i++) {
for (int j = 0; j < getRowDimension(); j++) {
arr[i][j] -= a.arr[i][j];
}
}
}

public String toString() {


String s = "";
for (int i = 0; i < getColumnDimension(); i++) {
for (int j = 0; j < getColumnDimension(); j++) {
s += arr[i][j] + ", ";
}
s += "\n";
}
return s;
}
}
```

ach ja also JAvaEditor sagt mir das ander zeile 44 ein fehler liegt


----------



## hfu (3. Apr 2010)

Wo hast du denn die Klasse Matrix?

Und versuche doch 
a) Klassennamen groß zu schreiben 

```
public class Matrizen
```

auch in den Konstruktoren dann wieder Matrizen groß schreiben

und b) 
den Code etwas einzurücken


----------



## BoZoM (3. Apr 2010)

also auch wenn ich da ne neue klasse mache namens Matrix bleibt der fehler gleich.


----------



## hfu (3. Apr 2010)

Wenn du keine Klasse "Matrix" hast, was ist dann das? 
	
	
	
	





```
Matrix c = new Matrix(n, m);
```
oder das hier? 

```
public Matrix plus(Matrix a) {
 
 
int m = getColumnDimension();
int n = getRowDimension();
Matrix c = new Matrix(m, n);
 
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
c.arr[i][j] = arr[i][j] + a.arr[i][j];
}
}
return c;
}
```


----------



## BoZoM (3. Apr 2010)

ne ich dachte eher daran so zu schreiben


```
public class Matrizen
```

aber dies war blödsinnig.


----------



## hfu (3. Apr 2010)

Hast du das alles selbst geschrieben? 

Meinst du dann statt der Matrix immer Matrizen? 
Dein Compiler kennt Matrix nicht, was soll das sein? 
Da du keine Klasse "Matrix" besitzt, kann er damit nichts anfangen.

Überleg dir besser noch einmal was dein Programm genau bewirken soll.
Deine Methoden sollten klein beginnen und zusammengeschrieben werden.

Nicht public 
	
	
	
	





```
static matrizen matmult(matrizen a, b) {
```
sondern 
	
	
	
	





```
public static matrizenMatmult(matrizen a, b) {
```

Aber was dein Programm genau tun soll, hat sich mir nocht nicht so ganz erschlossen.


----------



## BoZoM (3. Apr 2010)

also meine idee ist es das 2 matrizen generiert wird und die werden halt mit +,-,*=... berechnet


----------



## hfu (3. Apr 2010)

Willst du die beiden Matrizen miteinander multiplizieren, oder geht es um die werte mit denen du die Matrix füllst?


----------



## BoZoM (3. Apr 2010)

ich will sie miteinander multiplizieren und am ende soll auch noch stehen wie lange für die rechnung gebraucht wurde für die jeweiligen operationen


----------



## hfu (4. Apr 2010)

Also Arrays zu addieren oder zu multiplizieren ist gar nicht so schwer. 

Du hast zB. 3 Arrays: arr1; arr2 und arr3.

Willst du arry & arr2 multiplizieren und in 3 das Ergebnis speichern sieht das ungefähr so aus:


```
for (int i = 0; i<arr1.length; i++) {
   for (int j = 0; j <arr1[i].length; j++) {
      arr3[i][j] = arr1[i][j] * arr2[i][j];
   }
}
```


----------

