Komplexität O(n)
-
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.
