Komplexität O(n)

Daniel E.

_et schrieb:

Wäre es dennoch korrekt, wenn ich für den Aufwand eines Verfahren der Quantität n sagen, daß ein Verfahren O(n) oder O(2n), O(n) oder O(n+1)? Einfach um zu sagen, daß das eine Verfahren linear abhängig davon ist, aber eben doppelt so lange dauert. Oder das andere linear an der Quantität hängt, aber immer einen Schritt extra braucht.

Wenn Du so etwas ausdrücken willst, dann ist O-Notation nicht besonders geeignet.

Jeder Algorithmus mit O(n) ist auch von der Ordnung O(n^n) (natürlich schätzt so nur ein Depp ab, aber die übliche Definition aus Jesters Beitrag gibt das halt her) ... für viele Problemstellungen kann man auch nicht sagen, daß der Algorithmus von der Art O(n) ein Problem schneller löst, als einer von der Art O(n^2), weil der O(n)-Typ hohe 'Fixkosten' hat (bspw. den Aufbau einer Tabelle oder sowas). Mit der O-Notation gibt man asymptotisches Verhalten an, also gibt es irgendeine Problemgröße, wo der O(n)-Algorithmus den O(n^2)-Typ überholt, aber vielleicht liegt diese Grenze absolut außerhalb des 'üblicherweise' interessanten Problemrahmens. Oder der O(n^2)-Algorithmus hat durchschnittlich eine bessere Laufzeit als ein O(n log n)-Algo, nur das worst-case-Verhalten ist schlechter ...

Lange Rede, kurzer Sinn: Wenn Du primär Laufzeiten vergleichen willst, dann vergleiche Laufzeiten und kein asymptotisches Verhalten im worst case. Die Klassifikation in der O-Notation kannst Du ja trotzdem dazuschreiben ...

Hallo!

Welche Komplexität hat eigentlich folgender Algorithmus?

23+10/n² O(g(n)) bzw. O(f(n))=??

Käme da O(10/n²) heraus? oder wie berechne ich O(n) bei 1/n² ??

Oder muss man 23+10/n² <= 23/n² + 10/n² = 33/n² auf die Art beweisen?

Also O(33/n²) ?? Oder ist es schlichtweg O(n²)?? Aber O(1/n²) ist wohl performanter als O(n²), da liegen doch Welten zwischen.

Danke!

CStoll

Erstens ist es hier nicht besonders gern gesehen, uralte Beiträge aus der Versenkung zu ziehen, um darin neue Fragen zu stellen.

oldewolbers schrieb:

Hallo!

Welche Komplexität hat eigentlich folgender Algorithmus?

23+10/n² O(g(n)) bzw. O(f(n))=??

Zweitens ist das kein Algorithmus, sondern nur eine Formel.

Und drittens: Wenn diese Formel die Laufzeit eines Algorithmus darstellt, fällt der unter konstante Laufzeit (d.h. O(1)) - egal wie groß n ist, der Wert wird niemals größer als 33.
(aber welcher Algorithmus benötigt weniger Zeit, je größer die Eingabe ist?)

SeppJ

CStoll schrieb:

(aber welcher Algorithmus benötigt weniger Zeit, je größer die Eingabe ist?)

void schneller_werdende_identität(int *data, int N)
{
 sleep(23 + 10/N/N);
}

:p

CStoll

SeppJ schrieb:

:p

Ich präzisiere: aber welcher praktisch sinnvolle Algorithmus benötigt weniger Zeit, je größer die Eingabe ist?

Bashar

Eine Turingmaschine, die floor(10000/n) im Unärsystem ausgibt?

SeppJ

Bashar schrieb:

Eine Turingmaschine, die floor(10000/n) im Unärsystem ausgibt?

Hmm, aber die Division wäre nicht konstant, oder?

Bashar

Das kann man durch ein paar Vergleiche machen, es gibt ja nur endlich viele Werte. Es war aber nur so als Idee gedacht. Am Ende ist das sowieso nur O(1) und damit relativ uninteressant.

Jester

O(1/n^2) ist teilmenge von O(1), aber meist braucht man sowas eher um fehlerterme abzuschätzen, da ist dann wichtig, dass das gegen 0 geht und eben nichtnkonstant bleibt.

CStoll schrieb:

Ich präzisiere: aber welcher praktisch sinnvolle Algorithmus benötigt weniger Zeit, je größer die Eingabe ist?

wie wär's mit dem da:

Eingabe: n Fische in einem Teich von fester Größe
Ausgabe: irgendein Fisch aus dem Teich

Algorithmus: 

while(nochKeinFischGefangen)
  wirfAus(Netz);

Komplexitätsanalyse: je größer n, desto eher fängt man einen

SeppJ

Korinthenkackererwiderung:
`

return ersten_fisch_aus_der_eingabe;`

Komplexität: Konstant.

Du müsstest noch leere Teichfelder mit übergeben, damit dein Algorithmus überhaupt Sinn macht, aber dann ist die Eingabemenge von der Größe des Teiches abhängig und die Laufzeit ist dann eine Funktion der Fischdichte

Jester

du hast aber einen anderen algorithmus angegeben. die frage war ja nach einem algorithmus, der soneine komplexität hat, nicht ein Problem, das diese Komplexitaät hat...

Jester schrieb:

du hast aber einen anderen algorithmus angegeben. die frage war ja nach einem algorithmus, der soneine komplexität hat, nicht ein Problem, das diese Komplexitaät hat...

Wie kann etwas eine Komplexität haben, das nicht einmal notwendigerweise terminiert?

Jester

zum beispiel die erwartete laufzeit? das ist durchaus üblich, google mal nach Las Vegas Algorithmen.

Version 2.0 (n jetzt nicht mehr Teil der Eingabe):

Parameter: ein leerer Teich von fester Größe, Zeitkonstante t (ein paar Monate)
Eingabe: eine Menge markierter Fische M
Ausgabe: irgendein Fisch aus dem Teich, der nicht markiert ist (also der Nachzucht entstammt)

Algorithmus: 

setzeInDenTeich(M);
wait(t);
while(nochKeinUnmarkierterFischGefangen)
  wirfAus(Netz);

je größer die Eingabe |M|,
desto mehr Nachzucht,
desto schneller fängt man einen unmarkierten Fisch.

der Teich und die Ausgabe sind jetzt beide nicht mehr Teil der Eingabe.

Jester

in einen teich von fester größe passt aber nur eine ste anzahl fische.

auf das begrenzte Band einer physikalischen Turingmaschine passen nur begrenzte Eingaben - finden wir uns damit ab

The first rule of the tautology club is the first rule of the tautology club. Finden wir uns doch lieber damit ab

das die Tragödie der Komplexitätstheorie - im real life ist alles O(1)