Fragen :Effizienz ,Vereinfachen von Ausdrücken

Haggard

Hallo zusammen , ich habe hier Fragen , die ich gelöste habe und ich würde gerne wissen , ob die Ergebnisse richtig sind oder nicht .

die erste Aufgabe ist nach Landau-Notation

double c[n][n];
for (int i = 0 ; i < n ; i++) {                          // hier : n 
for (int j = 0 ; j < n ; j++) {  
c[i][j]= a[i][j]+ 2*b[i][j];                                 // 2n

   }
}


// kommt O(n² )  raus ?.
 
Vereinfachen von diesen folgenden Ausdrücken :

O(n² /n³ + 1/n³ + 1/n : o(1/n).

O(n²-2n³+n³): n²

O(n hoch (2.5)+ n²) : O( n hoch (2.5))
.

Vielen Dank im Voraus , ich freue mich auf eure Antworten .

wob

Verstehe den Kommentar "// 2n" in dem Schleifenörper nicht. Aber ja, 2 Schleifen, die beide von 0..n loopen und im Scheifenkörper eine O(1)-Operation machen, sind $\mathcal O(n^2)$ . Natürlich vorausgesetzt, dass a.operator[] und/oder b.operator[] nicht irgendwie von n abhängen (wer weiß, was a und b sind... - außerdem sind die eckigen Klammern nicht balanced, das kompiliert also sowieso nicht...)

Fraglich ist $n^2-2n^3+n^3 = n^2 - n^3$ , weil diese Funktion für große Eingaben negativen Aufwand hat. Ergibt wenig Sinn.

Haggard

@wob Danke dir !, ich habe mich verschrieben , es musste eigentlich geschlossen sein.

Finnegan

@Haggard sagte in Fragen :Effizienz ,Vereinfachen von Ausdrücken:

...

@wob sagte in Fragen :Effizienz ,Vereinfachen von Ausdrücken:

Fraglich ist $n^2-2n^3+n^3 = n^2 - n^3$ , weil diese Funktion für große Eingaben negativen Aufwand hat. Ergibt wenig Sinn.

Es ergibt Sinn, wenn man es nicht als "Aufwand" betrachtet, sondern einfach nur nach der mathematischen Definition geht:

$f \in \mathcal{O}(g) \Leftrightarrow \limsup\limits_{n\rightarrow\infty} \left| f(n) \over g(n) \right|\lt\infty$
(Hinweis: Leerzeichen zwischen lim und sup wird nicht gerendert)

Man beachte die Betraggstriche. Meines erachtens ist $\mathcal{O}(n^2 - n^3)=\mathcal{O}(n^3)$ .

Zum ersten Ausdruck:

Die Folge konvergiert gegen 0, somit gilt:

$\limsup\limits_{n\rightarrow\infty} \left| {n^2 \over n^3} + {1 \over n^3} + {1 \over n} \right|=0 \Rightarrow \mathcal{O}({n^2 \over n^3} + {1 \over n^3} + {1 \over n}) = \mathcal{O}(1)$

Finnegan

@wob sagte in Fragen :Effizienz ,Vereinfachen von Ausdrücken:

außerdem sind die eckigen Klammern nicht balanced, das kompiliert also sowieso nicht...

Ich frage mich gerade, ob nicht jeder Algorithmus, der für alle Eingaben sofort mit einem Fehler aussteigt $\mathcal{O}(1)$ ist ... aber ich will ja nicht wieder was lostreten

wob

Du hast recht. Ich habe das $\mathcal O$ bislang immer nur für Komplexität von Funktionen benutzt. Und da ergibt das mit Minus keinen Sinn. Aber stimmt, man sollte nach der Definition gehen - und dann gehts nur um das absolute Wachstum.

Finnegan

@wob sagte in Fragen :Effizienz ,Vereinfachen von Ausdrücken:

Du hast recht. Ich habe das $\mathcal O$ bislang immer nur für Komplexität von Funktionen benutzt.

Das ist wie mit dem Satz des Pythagoras und all den Dreiecken mit negativen Kantenlängen, die man als Lösungen erhalten könnte, sie aber einfach ignoriert. Da das aber so in der Aufgabe vorkommt, geht es hier wohl vornehmlich ums mathematische Verständnis

Swordfish

@Finnegan sagte in Fragen :Effizienz ,Vereinfachen von Ausdrücken:

Ich frage mich gerade, ob nicht jeder Algorithmus, der für alle Eingaben sofort mit einem Fehler aussteigt O(1) ist ... aber ich will ja nicht wieder was lostreten

Sorry, aber was willst Du damit lostreten? Natürlich ist

int foo(/* whatever */)
{
    return 42;  // O(1) oder eben O(von_was_es_braucht_die_fehleingabe_festzustellen)
    // whatever.
}

hustbaer

Ein Algorithmus der für alle Eingaben mit einem Fehler aussteigt ... huh? Entweder die Fehler sind nicht alle Fehler sondern es sind "nutzdaten" darin versteckt (z.B. im genauen Fehlercode/Fehlermeldung)... oder sonst würde ich mal in Frage stellen ob es sinnvoll ist sowas als "Algorithmus" zu bezeichnen.
Genau so wie ich return 42; oder sleep(10s); nicht als "Algorithmus" bezeichnen würde.

Finnegan

@hustbaer sagte in Fragen :Effizienz ,Vereinfachen von Ausdrücken:

Genau so wie ich return 42; oder sleep(10s); nicht als "Algorithmus" bezeichnen würde.

Ich bin da sehr liberal und bezeichne jede beliebige Abfolge von Anweisungen als Algorithmus, selbst die leere, die gar keine Anweisung enthält. Allerdings würde ich sowas nicht unbedingt als "sinnvollen Algorithmus" bezeichnen.

Auch ob der Algorithmus korrekt ist hängt davon ab, wie man das Problem definiert. Wenn mein Problem ist, dass ich für jede beliebige Eingabe die selbe Fehlermeldung erhalten möchte, dann ist der direkt in der ersten Anweisung einen Fehler werfende Algorithmus korrekt und O(1) auch wenn dahinter noch Code steht, der die Eingabe in O(n log n) nach Farbe sortieren könnte, wenn er denn zur Ausführung käme.

Das alles natürlich mit einem Augenzwinkern, mir ist auch bewusst, dass solche Betrachtungen von eher geringem praktischem Nutzen sind. Dennoch sind sie nicht falsch und helfen zumindest mir, bei theoretischen Überlegungen auch mal abseits der ausgetretenen Pfade um ein paar Ecken zu denken.

Aber keine Sorge, ich bezeichne std::sort auch als O(n log n), auch wenn es bei Problemen versagt, deren Größe nicht mehr in size_t passt - obwohl man als Gedankenspiel Problem und Lösung auch so umformulieren könnte, dass es O(1) ist

hustbaer

@Finnegan sagte in Fragen :Effizienz ,Vereinfachen von Ausdrücken:

Wenn mein Problem ist, dass ich für jede beliebige Eingabe die selbe Fehlermeldung erhalten möchte, dann ist der direkt in der ersten Anweisung einen Fehler werfende Algorithmus korrekt und O(1)

Klar. Kann man so definieren. Nur dann ist die Beschreibung "bricht mit einer Fehlermeldung ab" mMn. nicht sinnvoll. Denn dann hab ich im Prinzip einen Algorithmus definiert dessen Ergebnis eine Meldung ist und der keine Fehlerfälle hat. Bzw. das wäre mMn. die einzig sinnvolle Interpretation.

auch wenn dahinter noch Code steht, der die Eingabe in O(n log n) nach Farbe sortieren könnte, wenn er denn zur Ausführung käme.

Naja dann hat der Algorithmus "unreachable code". D.h. er ist vielleicht korrekt aber nicht sinnvoll formuliert.