Laufzeitkomplexität, O Notation
-
Hi,
Die Laufzeitkomplexität eines Algorithmus ist die obere schranke der Laufzeit die ein Algorithmus bei einer beliebigen anzahl von eigangswerten? die O notation ist sowas wie eine menge funktionen die unter dieser schranke sich befinden?
kann mir jemand ein gutes skript zu datenstrukturen & algorithmen empfehlen?
lg
-
Es ist die Laufzeit in Abhängigkeit von den Eingangswerten. Wenn Du ein 2D Array hast mit n Spalten und n Zeilen und Du alle auf den Bildschirm der Reiche nach ausgeben willst, ist das beste was Du (Dein Algo) erreichen kannst O(n²).
-
weil eine schleife n hat und 2 verschachtelte schleifen n^2 ?
aber es ist doch einen maximale laufzeit, dh der algo kann nicht langsamer sein...aber schneller sein...wenn man die konstanten einrechnet...
cu
-
das beispiel war falsch. die repräsentation der daten spielt keine rolle. man kann es sich umgangssprachlich ganz gut merken als "wieviele objekte muss ich maximal anfassen, um die gewünschte information zu erlangen?"
im beispiel muss man alle daten einmal anfassen (einlesen, darstellen), es hat als lineare komplexität. die anzahl der "zugriffe" steigt linear mit anzahl der eingangsdaten, also O(n).
-
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=
-
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.