Algorithmus Aufgabe
-
Für ein bestimmtes Problem stehen vier unterschiedliche Algorithmen mit unterschiedlichen Laufzeitkomplexitäten zur Verfügung:
A: ld(n) B: n C: n2
2nWelchen Algorithmus würden Sie für ein kleines Problem n = 500 verwenden
also ich würd natürlich den ld(n) verwenden. Oder lieg ich falsch ?
-
Die Frage ist nicht beantwortbar, da die konstanten unbekannt sind. Dazu zwei Fragen: Was soll ld sein? Was soll 2n bei D bedeuten?
Allgemein: Wenn n klein wird, ist nicht automatisch der Algorithmus mit der besten Komplexitätsklasse der Beste. Beispiel Sortieren: Für kleine n hängt selbst Bubblesort ausgefallene Algorithmen wie Mixsort ab, eben weil Mixsort große Konstanten hat, Bubblesort nicht.
-
HI SeppJ,
also n ist die Anzahl der Eingabedaten. Die Algorithmen laufen
auf gleichen Rechnern.
-
C:n^2
2*n
-
Nachdem ld() mit 8,x den kleinsten Wert liefert, nimmst du den Algorithmus A.
Bei n=500 haben sich die meisten Standard-Algorithmen ohnehin schon in ihre Kategorie eingependelt. Komische Frage.
MfG SideWinder
-
nehmen wir mal n=10 an . Welcher ist dann der schnellste ?
-
berechne doch einfach : ld(10 vs 10 vs 10^2 vs 2*10
nimmste den, der das Kleinste Ergebnis liefert.
-
so einfach geht das doch nicht.
Wie ein Kollege vorher schon erwähnte schlägt bubble sort so manchen
komplexen Algorithmus wenn es um kleine Eingabewert geht
-
Da hier exakte Komplexitäten, keine Landausymbole, angegeben sind, kann man wohl einfach den ld nehmen.
(Nebenbei wär die Aufgabe ziemlich dämlich, wenn da O(ld n) usw. stehen würde. Nicht dass es keine dämlichen Aufgaben gibt ...)
-
Bashar schrieb:
Da hier exakte Komplexitäten, keine Landausymbole, angegeben sind, kann man wohl einfach den ld nehmen.
Der Begriff "Laufzeitkomplexitäten" aus der Aufgabenstellung impliziert doch wohl das Landausymbol.
