Laufzeitkomplexität, O Notation
-
Wenn die Eingabe aus quadratischen Arrays besteht kann die Kantenlänge sicherlich als Kriterium gewählt werden.
@Algoman:
Ja, zwei verschachtelte Schleifen, deshalb wird n² mal etwas ausgegeben bzw auf das Array zugegriffen.
Welche O Notation meinst Du genau? Gross O?Zur Konstante:
LaufzeitDeinesAlgo = O(f(n)) meint das die Laufzeit des Algorithmus nicht stärker wächst als k*f(n). Wobei k ein Konstante sein muß.Nehmen wir an die Arrayelemente müssen 2 mal angefasst werden (zB Vergleich ob Element>0 und wenn ja dann Ausgabe) dann hat man im schlimmsten Fall 2*n² Arrayzugriffe. Ist dann aber trotzdem O(n²).
PS: Auch O(n³) wäre eine obere Schranke für das obige Arrayproblem. Bei groß O wird ja nicht nach der kleinsten obereb Schranke gefragt.
-
this->that schrieb:
O(g) ist die Menge aller Funktionen f, die ab einem Grenzwert n0 bis auf einen konstanten Faktor <= g sind.
http://users.informatik.haw-hamburg.de/~voeller/th/thinf/node27.html
Zum A&D Skript:
http://www.google.de/search?hl=de&as_qdr=all&q=algorithmen+skript&btnG=Suche&meta=von was hängt n0 ab? und was ist g?
-
n0 meint das die Laufzeitabschätzung nicht für kleine Eingaben gelten muß. Wenn das Programm in Java ist wird erst die Java Runtime gestartet. Bei einer kleinen Eigabe fällt das Starten der JVM stärker ins Gewicht, bei großen Eingaben nicht mehr. g ist die Funktion in der O Notation.
In meinem Fall war g(n) = n².
-
ich dachte f(n) ist die funktion in der notation? weil du geschrieben hast: O(f(n))
cu
-
In seinem Beispiel ist es genau andersrum.
-
martin_salo schrieb:
In seinem Beispiel ist es genau andersrum.
wo?
-
Is doch völlig Wurst ob man die Funktion f, g oder Hans nennt. Stell dir einfach die Funktion in dem O als die "nach oben beschränkende Funktion" vor.
-
welche zeitkomplexität hat die binäre suche? logarithmisch?
cu
-
Ja.
(aber wenn du etwas gesucht hättest, hättest du das - inklusive der Erklärung/Beweis warum - auch selber herausgefunden)
-
Dieser Thread wurde von Moderator/in HumeSikkins aus dem Forum C++ in das Forum Rund um die Programmierung verschoben.
Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?Dieses Posting wurde automatisch erzeugt.