Effizienz (Zeit und Speicher) von Algorithmen berechnen (mathematisch)

[k00ni]

Heute hatten wir im ersten Seminar zu \"Algorithmen und Datenstrukturen\", Übungen für die Berechnungen der Effizienz von Algorithmen. In den ersten 50 Minuten hab ich mich in der Vorlesung dazu gefragt, was nun eigentlich Sache ist; erst in der Übung kam dann etwas Licht ins Dunkel.
Für alle, die immer noch nicht wissen, wovon ich rede: es geht darum, dass man mittels mathematischer Mittel und diverser anderer Dinge bestimmen kann, ob ein Algorithmus besonders Zeit- oder Speicherintensiv geschrieben wurde. Dabei bezieht man sich auf die Auswertung oder die Bearbeitung von endlichen Datenmengen, wie bspw. Zahlenlisten.
Vorhin dachte ich mir, dass man dass ja auch bei PHP und besonders im Zusammenhang mit MySQL (bzw. allgemein Datenbanken) gebrauchen könnte. Vielleicht wäre es ja mal lustig, Teile des pSys zu analysieren und zu schauen, wie \"effizient\" der Powie gearbeitet hat. /uploads/emoticons/icon_e_surprised.gif.a8707b3f35a569cb4cfe563fc72ef78d.gif\" alt=\":-o\" />
 
Grüße

Vorhin dachte ich mir, dass man dass ja auch bei PHP und besonders im Zusammenhang mit MySQL (bzw. allgemein Datenbanken) gebrauchen könnte. Vielleicht wäre es ja mal lustig, Teile des pSys zu analysieren und zu schauen, wie \"effizient\" der Powie gearbeitet hat.[/quote]
Du meinst, wie unter http://storage.cj-soft.de/powie/psys_image_benchmark/\" rel=\"external nofollow\">http://storage.cj-soft.de/powie/psys_image_benchmark/  geschehen?

[k00ni]

Nein, eher in dieser Richtung. (Auszug aus den Folien des Profs.):
 

O-Notation (obere Schranke)
Klasse der Funktionen O(f), die zu einer Funktion (Größenordnung) f gehören
ist O(f) = {g | ∃c > 0 ∃n0 > 0: ∀n ≥ n0 : g(n) ≤ c · f(n)}
– Die Funktion f(n) majorisiert g(n)
Beispiel: 6n4 + 3n3 - 7 n ∈ O(n4)
-----------------------
Ω -Notation (untere Schranke)
Ω (f) = {g| ∃ c > 0 : ∃ n0 > 0 : ∀ n ≥ n0 : g(n) ≥ c f(n)}
g ∈Ω (f) oder g = Ω (f) drückt aus, dass g mindestens so stark wächst wie f.
– f(n) minorisiert g(n)
---------------------
Θ-Notation (Exakte Schranke)
Gilt für eine Funktion g sowohl g ∈ O(f) als auch g ∈ Ω (f), so
schreibt man g ∈ Θ(f)

 
 
Vielleicht haste damit schonmal was gemacht? Oder wir reden vielleicht gar vom selben? Ich bin da zur Zeit etwas durch den Wind /uploads/emoticons/icon_e_biggrin.gif.1a84f5257b36e14b36d04985314f877f.gif\" alt=\":-D\" />
[Edit]Scheisse, hier werden alle Sonderzeichen maskiert und in HTML-Tags geändert.  ;-(  Wie kann ich das umgehen?[/edit]
Grüße

Vielleicht haste damit schonmal was gemacht? [/quote]
Sollen die umgesetzten Sonderzeichen (Entitiys) Landau-Symbole sein?

Oder wir reden vielleicht gar vom selben?[/quote]
Prinzipiell ja. Du beschreibst die Methoden, die zur Auswertung des oben gemachten Benchmarks geführt haben. Ich wollte das anwesende Publikum nicht mit Analysis langweilen. Dafür gibt es die schnieken Bildchen.

ch bin da zur Zeit etwas durch den Wind[/quote]
Neustudent?

Scheisse, hier werden alle Sonderzeichen maskiert und in HTML-Tags geändert.[/quote]
Das sind keine Tags, sondern numerische Entitys.

Wie kann ich das umgehen?[/quote]
Gar nicht. Hier wurde zu viel des Guten am Output modifiziert.

[k00ni]

Hallo,
ja ich bin Neustudent. Hat man dass an meiner Unwissenheit bemerkt? /uploads/emoticons/icon_e_biggrin.gif.1a84f5257b36e14b36d04985314f877f.gif\" alt=\":-D\" /> Die angegebenen Symbole sind aus dem Landau-System, davon habe ich bei Wikipedia gelesen, direkt stad da aber bei uns nichts. Das Problem ist, die Vorlesung dazu war fürn Arsch, da es keiner raffte und er mir auch nicht erklären konnte, wofür man dass in der \"realen Welt\" braucht. Ich bin gerade dabei die Vorlesungen neu aufzuarbeiten und zu ergänzen. Gut das noch andere Unis diesen Stoff online anbieten /uploads/emoticons/icon_e_surprised.gif.a8707b3f35a569cb4cfe563fc72ef78d.gif\" alt=\":-o\" />
 
Grüße

ja ich bin Neustudent. Hat man dass an meiner Unwissenheit bemerkt?[/quote]
Nein. An deinem Enthusiasmus und der völligen praxisferne deines Postings. Klar, man muss irgendwie ein System formulieren, aber in der realen Welt[tm] mit echter Arbyte[tm] ist sowas einfach überflüssig.

Das Problem ist, die Vorlesung dazu war fürn Arsch, da es keiner raffte und er mir auch nicht erklären konnte, wofür man dass in der \"realen Welt\" braucht.[/quote]
Deswegen sind Frischlinge in der realten Welt[tm] auch so wenig beliebt. Sie können dich zwar mit Formeln zutexten, aber kein FTP-Programm bedienen. Ein Kollege von mir fand recht drastische, blumige Worte.

[k00ni]

Nein. An deinem Enthusiasmus und der völligen praxisferne deines Postings. Klar, man muss irgendwie ein System formulieren, aber in der realen Welt[tm] mit echter Arbyte[tm] ist sowas einfach überflüssig.[/quote]
Scheinbar nicht. Ich habe in einem Seminar vom Lesenden gehört, dass dies beispielsweise bei der Optimierung von Tabellen und deren Zusammenspiel mit anderen Tabellen zum Tragen kommt. Oder bei der Optimierung von Suchalgorithmen. Damit kann man nämlich hochrechnen, ab wann ein Algorithmus abkackt.
Als Beispiel sei ein einfacher Suchalgorithmus gemeint, der sich selbst aufruft. (Rekursion) Dieser ist von exponentieller Komplexität, was soviel heißt, dass ein Aufruf von ihm, auch immer einen weiteren Aufruf von sich selbst beinhaltet. (n²) Bei 100 Datensätzen mag das noch gehen. Aber wenn es in die tausende oder höher geht, so wird n exponentiell anschwellen und der Rechner braucht ein Jahrhundert.
Wie und was, dass muss ich mir noch aufarbeiten. Ich habs erstmal weggelegt und vollende erstmal ein paar Übungsserien. Man mag es kaum glauben, aber Informatik besteht nicht nur aus Informatik.  /uploads/emoticons/icon_e_surprised.gif.a8707b3f35a569cb4cfe563fc72ef78d.gif\" alt=\":-o\" />
 
Grüße

Scheinbar nicht. Ich habe in einem Seminar vom Lesenden gehört, dass dies beispielsweise bei der Optimierung von Tabellen und deren Zusammenspiel mit anderen Tabellen zum Tragen kommt. Oder bei der Optimierung von Suchalgorithmen. Damit kann man nämlich hochrechnen, ab wann ein Algorithmus abkackt.[/quote]
Ich habe nicht bezweifelt, dass die Berechnungen sinnvoll sind. Im Gegenteil: Das gehört zum täglichen Geschäft. Aber man macht es üblicherweise nicht so akademisch.

Als Beispiel sei ein einfacher Suchalgorithmus gemeint, der sich selbst aufruft. (Rekursion) Dieser ist von exponentieller Komplexität, was soviel heißt, dass ein Aufruf von ihm, auch immer einen weiteren Aufruf von sich selbst beinhaltet. (n²) Bei 100 Datensätzen mag das noch gehen. Aber wenn es in die tausende oder höher geht, so wird n exponentiell anschwellen und der Rechner braucht ein Jahrhundert.[/quote]
Keine Ahnung ob es Leute gibt, die hier noch irgendwelche Formeln benötigen: Aber spätestens, wenn man mal rausgefunden hat, dass ein Algorithmus exponentiell skaliert, ist der Schluß daraus evident.

Wie und was, dass muss ich mir noch aufarbeiten. Ich habs erstmal weggelegt und vollende erstmal ein paar Übungsserien. Man mag es kaum glauben, aber Informatik besteht nicht nur aus Informatik.[/quote]
Sag nur. Ich habe die Wirtschaftsinformatik vorgezogen - bedeutet zwar, dass man sich zusätzlich mit Wirtschaftsmathematik rumplagen muss, aber es gibt wenigstens etwas Abwechslung.