Komplexitätsberechnung mit O-Notation

Aufrufe: 272     Aktiv: 23.07.2023 um 23:28
0

Hey, ich bin mir unsicher, ob meine Lösungen zu den beiden Aufgaben richtig sind.

Bei der ersten Aufgabe steht eine alternative Lösung zur Debatte und zwar: k × (l ×2) = 2×k×l = 2×n O(2n) = O(n)

Die alternative Lösung kommt daher, dass man die Eingabegröße beachtet. Ich dachte man muss das komplett ignorieren bei der Komplexitätsberechnung, bin mir aber trotzdem unsicher, vielleicht eine Erwähnung der Eingabegröße zur Verwirrung??

Bei der zweiten Aufgabe bin ich mir ziemlich sicher, dass es falsch ist, habe aber keine Ahnung wie ich es anders formal herleiten würde. Als Idee käme mir nur ein c und ein n0 zu finden, aber ehrlich gesagt keine Ahnung wie das gehen soll.

Diese Frage melden
gefragt

Punkte: 12

 
Kommentar schreiben
1 Antwort
1

Zunächst einmal ist anzumerken, dass die Frage eher was für informatik-fragen.de ist.

Zu Aufgabe (1): Dein Denkfehler liegt darin das du denkst die ersten beiden for-Schleifen haben eine Laufzeit von $O(n)$. Innerhalb welcher Grenzen laufen denn die Schleifen? Dann benutze das $n=k\cdot l$ gilt.

Zu Aufgabe (2): Was du aufgeschrieben hat ergibt keinen Sinn. Du sollst formal die Definition benutzen. Findest du ein $c$ und ein $n_0$, so dass für alle $n\geq n_0$ gilt: $f(n)\leq c\cdot g(n)$?

Diese Antwort melden
geantwortet

Punkte: 8.85K

 
Das Informatikforum ist ziemlich eingeschlafen und ehrlich gesagt ist, bis auf die Code-Anwendung alles mathematischer Natur, deshalb :).

Zu Aufgabe (1), ich habe mir noch mal genauer überlegt, wieso meine Überlegung nicht stimmt. Im Grunde ist die richtige Begründung, dass man ja Matrizen berechnen soll, da man nicht davon ausgehen kann, dass es nur quadratische Matrizen gibt. Wäre das der Fall, würde meine Lösung stimmen. Die Alternativlösung gilt damit für jede beliebige Matrix. (im Text über meinem Rechengekrakel)

Zu Aufgabe (2): da fehlen mir die Vokabeln zur Definition, ich konnte sie nicht wirklich verstehen. Weiterhin: wie genau gehe ich denn vor, um ein ein c und ein n0 zu finden, dass der Definition entspricht?   ─   sebas4444 23.07.2023 um 19:13
1
Ja theoretische Informatik ist viel Mathematik und daher kannst du die Frage hier ruhig stellen.
Woher stammt denn die Alternativlösung, von dir oder aus einer vorgegebenen Lösung? Wie ist die Laufzeit von der ersten for-Schleife? Und wie von der zweiten? Und die Matrixoperation? Diese multiplizierst du, fasst sie zusammen und benutzt wie gesagt das $n=k\cdot l$ gelten soll. Und ja es muss sich nicht um quadratische Matrizen handeln.

Zu (2), setze doch einfach mal Werte ein für $n$ und versuche dann nach oben abzuschätzen ob du ein $c$ findest was dann für alle $n$ die größer als dein gefundenes die Ungleichung erfüllt. Probiere und poste gerne deine Gedanken.   ─   maqu 23.07.2023 um 19:32
Zu (1), das habe ich so gelöst. Fraglich nur an welcher Stelle es formal korrekt ist O(2) zu O(1) zu abstrahieren. https://pasteboard.co/BawYUdSzJmLw.png

Zu (2) was genau ist meine Ungleichung? Und was meinst du mit gefundenes bei
"was dann für alle n die größer als dein gefundenes " ?

   ─   sebas4444 23.07.2023 um 19:51
Ich hatte jetzt nochmal die Ruhe und habe selbst versucht eine Lösung zu notieren. Einfacher ist es glaube ich man wählt sich sein $c$ am Anfang geschickt und findet dann ein $n_0$. (Wenn ich falsch liege bitte ich die Helfys die noch aktiv mit dem Unistoff zu tun haben mich zu korrigieren) In der Definition steht ja $\exists$, als es existiert ein …. Du musst also nur etwas Zahlen für $c$ und $n_0$ finden sie dass deine Definition erfüllt ist.

Also sei angenommen $c=2$. Was erhältst du dann für $c\cdot g(n)$? Nun solltest du doch sicherlich selbst drauf kommen einen Punkt zu finden ab dem $f(n)\leq c\cdot g(n)$ erfüllt ist, oder? Diese Ungleichung soll erfüllt sein damit du sagen kannst das $f\in O(g)$ erfüllt ist.

(1) sieht so in Ordnung aus denke ich. Alle Konstanten liegen in $O(1)$, das ist also ok.   ─   maqu 23.07.2023 um 20:25
Also für mich ist die aktuelle Lösung von (1) ein Durcheinander von Kürzeln, ohne irgendeine Erklärung und Begründung. O(2) u.ä. macht überhaupt keinen Sinn. Versuch es mal mit Text aufzuschreiben, das hilft enorm beim Verständnis
Genauso ganz oben mit (2): Da steht z.B. f=g, was ganz offensichtlich nicht der Fall ist. Also, auch hier: Drück Dich nicht um den Text herum, wenn Du es verstehen willst.
Schreib die geforderte Ungleichung hin und bedenke, dass Du das c selbst wählen darf. Schreib die Ungleichung für verschiedene (selbstausgedachte) c hin und schau, ob und falls nötig, ab welchem n0 das erfüllt ist.
Hat maqu auch schon gesagt, aber manchmal hilft es ja, wenn jemand anders dasselbe nochmal formuliert. Vor allem: verwende Text in Deinen Notizen.   ─   mikn 23.07.2023 um 23:28

Kommentar schreiben