Komplexität Algorithmus
-
Es gibt sogar Linearzeit-Algorithmen, die praktisch unbrauchbar sind, weil der konstante Vorfaktor c in der Darstellung zu groß ist.
Was ist mit dem Vorfaktor c genau gemeint?
-
Komplexität 2er Algorithmen.
1. 100 * n
2.n^2bei kleinen Eingabedaten wäre der 2. trotzdem besser.
-
Wenn du weißt, was Linearzeit ist, dann weißt du, was O-Notation ist, und wenn du das erklären kannst, weißt du auch, was für ein Vorfaktor da gemeint ist.
-
zum beitrag von blurry6235:
1. 100*n, der Vorfaktor c ist 100
2. n², der Vorfaktor c ist 1Graphisch um es besser zu verstehen:
http://img524.imageshack.us/img524/8021/kurve.pngfür n<100 ist 2. Effektiver für n>100 ist 1. Effektiver.
-
A: ld(n) B: n C: n^2
2^nWelchen Algorithmus würden Sie für ein kleines Problem der Größe n=500 verwenden.
Laut der Lösung soll es Algorithmus D sein. Ich hab momentan keine
Ahnung wieso das so sein könnte ?
-
Das ist die vollständige Aufgabe. Kann sie mir einer erklären.
Wäre super.http://www.bilder-space.de/show.php?file=31.01RiJbKxQq0nYOCgd.JPG
-
die Teilaufgabe b macht mir halt noch zu schaffen
-
Ich kann mir nicht vorstellen das 2^n die Lösung sein soll...
2^n Steigt dermaßen stark an, dass schon bei Eingaben von n=5, alle anderen Laufzeiten schneller sind(Ohne Vorfaktoren).Geschweige denn bei n=500
2^500=3'000'000'000'000'000'000'000'000'000'000'000'000'000'000'000'000'000'000'00'000'000'000'000'000'000'000'000'000'000'000'000'000'000'000'000'000'000'000'000'00'000'000'000'000'000'000'000'000'000'000'00 [Rechenzeit].Und das ist nicht übertrieben!
im Vergleich zum zweit schlechtesten n² mit "nur" 250'000 [Rechenzeit].
Da ist was faul...
-
Die Lösung stimmt.
Aus der Angabe von 60 min für n = 1000 kann man die Vorfaktoren c für jeden Algorithmus ermitteln:
A: 6
B: 0,06
C: 0,00006
6/(10^300)Wenn man jetzt n = 500 einsetzt erhält man die neuen Laufzeiten (in min):
A: 53
B: 30
C: 15
18/(10^150)Wobei letzteres eindeutig der kleinste Wert ist --> Algorithmus D.
edit: Grafisch: http://www1.xup.in/exec/ximg.php?fid=35879792
(A blau, B grün, C rosa, D lila
-
@wx++
Das stimmt, auch wenn es ein bischen hingebogen aussieht. Denn aus der Aufgabenstellung geht nicht hervor, dass jeder Algorithmus genau 60 Minuten braucht.
Dieses "Innerhalb" in der Aufgabenstellung vermittelt dem Leser, dass keiner der Algorithmen länger als 60 Minuten braucht, nicht aber das die Algorithmen jeweils "genau" oder "in etwa" 60 Minuten brauchen.
Ein bischen schwammig die Aufgebenstellung, oder ich bin da zu penibel...Wenn ich mir dann noch den Vorfaktor von
18/(10^150)ansehe, dann sieht das SEHR dahingebogen aus; Ein Faktor der schon jenseits aller Meßbarkeit an null rangeht....
-
Ist vielleicht schwammig formuliert aber ohne diese Betrachtungsweise ist die Aufgabe Nonsens, da man dann faktisch keine Angaben über konkrete Laufzeiten hat.
edit:
dann sieht das SEHR dahingebogen aus;
Ich habe nichts "hingebogen". Dass die Aufgabenstellung eine rein theoretische Situation darstellt, ist klar.
-
Zitat:
dann sieht das SEHR dahingebogen aus;Ich habe nichts "hingebogen". Dass die Aufgabenstellung eine rein theoretische Situation darstellt, ist klar.
Ich meinte auch nicht, dass du etwas dahingebogen hast, sondern der Schlaukopf der sich die Aufgabe fern aller Realität ausgedacht hat.
-
Klar. Ein Algo, der Probleme < 1000 in nicht messbarer Zeit löst und unmittelbar darüber ins Unendliche abzischt ist nicht sehr realistisch.
ps: Vielleicht reicht der Arbeitsspeicher für den Algorithmus nur bis n=1000 und danach muss auf Lochkarten ausgelagert werden.
-
wx++ schrieb:
Aus der Angabe von 60 min für n = 1000 kann man die Vorfaktoren c für jeden Algorithmus ermitteln
Bist du sicher, dass man das kann? Die O-Notation abstrahiert auch von additiven Konstanten.
-
Stimmt, aber wenn die wesentlich sind ist die Aufgabe wieder nicht lösbar.
Wir einigen uns auf eine schlechte Aufgabenstellung, ok?
-
wx++ schrieb:
Wir einigen uns auf eine schlechte Aufgabenstellung, ok?
Würde ich auch sagen. Nachdem D die richtige Lösung sein soll, wäre es nett wenn wir irgendwann erfahren wie der Aufgabensteller argumentiert. Kann mir nicht vorstellen, dass da was Vernünftiges dabei herauskommt.
-
Noch eine Frage .
C_n=max(1+C_n-1,1+C_n-2)
=1+max(C_n-1,C_n-2)
=1+C_n-1Ich frag mich gerade was diese max Funktion soll ?
-
blurry333 schrieb:
Ich frag mich gerade was diese max Funktion soll ?
vielleicht ist es die std::max?
-
Die funktion scheint dir das Maximum der beiden übergebenen Paramter zurückzugeben. Wobei mir das rausziehen der 1 aus der Max-funktion komplizierter aussieht als einfach direkt auszuwerten...
a := C_nAusführlich:
C_n = max(1+C_n-1,1+C_n-2) //Anfangsterm
a = max(1+a-1,1+a-2) //Substituiert C_n = a
a = max(a+1-1,a+1-2) //Sortiert
a = max(a+0, a-1) //Größeren der beiden Terme finden mit max
a = a //Aussagen sind äquivalent
C_n = C_n //Rücksubstitution a = C_n
-
@JaykopX
http://de.wikipedia.org/wiki/Schildb%C3%BCrger@blurry333
Wie wäre es, wenn du, statt die Fragen einfach so einsilbig hinzuschnmieren, mal den Kontext erklärst, damit die hilfbereiten Poster hier wissen um was es geht und sich nicht so verzetteln müssen wie oben.
-
Hi,
wenn bei den Sortierverfahren von log die Rede ist , meint man
doch immer den zur Basis 2 ??
