Komplexität Algorithmus

JaykopX

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...

wx++

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

JaykopX

@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....

wx++

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.

JaykopX

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.

wx++

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.

wx++

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.

blurry333

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-1

Ich frag mich gerade was diese max Funktion soll ?

volkard

blurry333 schrieb:

Ich frag mich gerade was diese max Funktion soll ?

vielleicht ist es die std::max?

JaykopX

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_n

Ausfü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 ??

http://de.wikipedia.org/wiki/Sortierverfahren

Hank Chinanski

Guck Dir mal an wie die O-Notation funktioniert, dann erledigt sich Deine Frage von selbst

Ah die Basis des Logarithmus ist egal. Hängt wohl damit zusammen dass
es immer ein konstanter Vorfaktor ist, um den sich die Logarithmen unterscheiden. Mehr weiß ich allerdings auch nicht.

JaykopX

@HurgaHurga
sorry

lieg ich falsch oder wie soll ich das verstehn

Was mich auch noch intressiert. Beim Bubble Sort soll der best case O(n) sein.
Aber ich kenn keinen Algorithmus der bei der vorsortierten Liste dies
erkennt und dann abbricht.

JaykopX schrieb:

@HurgaHurga
sorry
->http://de.wikipedia.org/wiki/Asperger-Syndrom

Ich mache dir keinen Vorwurf, dass du nicht im Geringsten verstanden hast, was blurry333 mit der Frage meint, denn er vergisst den Zusammenhang zu erwähnen und die Notation ist auch nicht hilfreich.

Wenn du allerdings aus einem einfachen 3-Zeiler durch seltsame Substitutionsmechanismen einen 6-Zeiler mit Nonsens-Ergebnis machst musst du dir schon etwas Kritik gefallen lassen. Und ein Link auf die Schildbürger schien mir nicht so hart wie das eigentlich angebrachte Dieter Nuhr Zitat.