Komplexität O(n)
-
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!
-
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?)
-
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
-
SeppJ schrieb:
:p
Ich präzisiere: aber welcher praktisch sinnvolle Algorithmus benötigt weniger Zeit, je größer die Eingabe ist?
-
Eine Turingmaschine, die floor(10000/n) im Unärsystem ausgibt?
-
Bashar schrieb:
Eine Turingmaschine, die floor(10000/n) im Unärsystem ausgibt?
Hmm, aber die Division wäre nicht konstant, oder?
-
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.
-
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
-
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
-
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?
-
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.
-
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)
-
Jester schrieb:
in einen teich von fester größe passt aber nur eine ste anzahl fische.
Hmm... Ein Fisch passt rein. Mit notfalls etwas drücken passt auch noch ein weiterer rein. Per vollständiger Induktion folgt das beliebig viele rein passen.
Wer das net hinkriegt drückt einfach nicht fest genug.
PS: Js der war schlecht.
