Laufzeitfunktionen und Ausführungszeiten

B

BoZoM

Mitglied
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
 
B

BoZoM

Mitglied
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

Final_Striker

Top Contributor
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.
 
Zuletzt bearbeitet:
0x7F800000

0x7F800000

Top Contributor
Imho kann man den letzten eintrag der ersten zeile sowas von knicken... :eek:
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...
 
0x7F800000

0x7F800000

Top Contributor
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.
 
B

BoZoM

Mitglied
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
 
Zuletzt bearbeitet:
B

BoZoM

Mitglied
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
 
B

BoZoM

Mitglied
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

Final_Striker

Top Contributor
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. ;-)
 
0x7F800000

0x7F800000

Top Contributor
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.


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
Zum Vergrößern anklicken....
Intervallhalbierungsverfahren? gut. :applaus:
Arrays? Blödsinn. :noe:

Final_Striker hat gesagt.:
Wir hatten im letzten Semester in der Algorithmen Vorlesung die Matrizen-Multiplikation behandelt. :)
Zum Vergrößern anklicken....

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

Final_Striker

Top Contributor
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
Zum Vergrößern anklicken....

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. ;-)
 
B

BoZoM

Mitglied
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;
}
}
 
B

BoZoM

Mitglied
aso wuste ich nicht hier nochmal dann:


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

hfu

Mitglied
Wo hast du denn die Klasse Matrix?

Und versuche doch
a) Klassennamen groß zu schreiben
Java: 
public class Matrizen

auch in den Konstruktoren dann wieder Matrizen groß schreiben

und b)
den Code etwas einzurücken
 
H

hfu

Mitglied
Wenn du keine Klasse "Matrix" hast, was ist dann das?
Java: 
Matrix c = new Matrix(n, m);
oder das hier?
Java: 
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;
}
 
B

BoZoM

Mitglied
ne ich dachte eher daran so zu schreiben

Java: 
public class Matrizen

aber dies war blödsinnig.
 
H

hfu

Mitglied
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
Java: 
static matrizen matmult(matrizen a, b) {
sondern
Java: 
public static matrizenMatmult(matrizen a, b) {

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

hfu

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

BoZoM

Mitglied
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
 
H

hfu

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

Java: 
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];
   }
}
 

Aktuelle Jobs

Neue Themen


Oben