Komplexitätstheorie - Average Case Laufzeit eines Algortihmus
-
volkard schrieb:
dot schrieb:
Dann kopier eben rum, das geht alles in O(n), hat also keinen Einfluss auf die Laufzeitkomplexität...
Ich denke, er will es stabil in dem Sinne, daß die Reihenfolge der Erstauftretungen der Werte erhalten bleibt.
Da sehe ich nicht, wie du nach dem Sortieren was zurückkopieren kannst und irgendwie kostengönstig die alte Reihenfolge findest.Ich häng an jedes Element in der Kopie noch den Index im Original an. Wenn mir wirklich nichts besseres einfällt, dann sortier ich die Kopie am Ende eben nochmal nach diesem Index, is ja scheissegal, Komplexität und so
-
volkard schrieb:
Sagen wir mal, ein int kann 4294967296 verschiedene Werte annehmen und das ARray habe n ints drin.
Dann nimmst Du Dir einfach alle möglichen Arraybelegungen, also alle 4294967296^n Stück und berechnest jeweils die Kosten und berechnest den Durchschnitt.Klingt nicht gerade besonders effizient, da muss es doch was einfacheres geben? Außerdem ist ja ^n nicht berechenbar, wenn ich allgemein bleiben möchte.
dot schrieb:
Nö wieso, ich hab doch ne bessere Laufzeitkomplexität!?
Bringt dir aber nix, weil ich zaubern kann.
dot schrieb:
Da hast du zwar recht, aber für die Laufzeitkomplexität spielt das keine Rolle.
Wenn du schon vom Thema ablenkst, dann kann ich hier ja wohl auch sagen, dass mir in diesem Fall die Theorie relativ egal ist. In der Praxis zählen solche Kosten, wie man z.B. bei Quicksort vs. Mergesort sehen kann.
dot schrieb:
Wenn wir von der Laufzeitkomplexität reden, dann reden wir vom asymptotischen Laufzeitverhalten. Die Notation mit Landau-Symbolen drückt genau das aus. Man beachte das "asymptotisch".
Gut, asymptotisch musste ich jetzt zugegebenermaßen googeln. Heißt doch aber auch nur "beliebig annähern"?
-
314159265358979 schrieb:
volkard schrieb:
Sagen wir mal, ein int kann 4294967296 verschiedene Werte annehmen und das ARray habe n ints drin.
Dann nimmst Du Dir einfach alle möglichen Arraybelegungen, also alle 4294967296^n Stück und berechnest jeweils die Kosten und berechnest den Durchschnitt.Klingt nicht gerade besonders effizient, da muss es doch was einfacheres geben?
Wer sagt, dass du das Bruteforce durchrechnen musst?
314159265358979 schrieb:
dot schrieb:
Da hast du zwar recht, aber für die Laufzeitkomplexität spielt das keine Rolle.
Wenn du schon vom Thema ablenkst, dann kann ich hier ja wohl auch sagen, dass mir in diesem Fall die Theorie relativ egal ist. In der Praxis zählen solche Kosten, wie man z.B. bei Quicksort vs. Mergesort sehen kann.
Wenn die Konstaten interessieren, dann hat es aber keinen Sinn von O(irgendwas) zu reden, denn O(irgendwas) ist genau die mathematische Art zu sagen: "Konstanten interessieren mich nicht"
314159265358979 schrieb:
314159265358979 schrieb:
dot schrieb:
Wenn wir von der Laufzeitkomplexität reden, dann reden wir vom asymptotischen Laufzeitverhalten. Die Notation mit Landau-Symbolen drückt genau das aus. Man beachte das "asymptotisch".
Gut, asymptotisch musste ich jetzt zugegebenermaßen googeln. Heißt doch aber auch nur "beliebig annähern"?
Das asymptotische Laufzeitverhalten ist eben das Verhalten der Laufzeit wenn N gegen unendlich geht...
-
dot schrieb:
314159265358979 schrieb:
dot schrieb:
In der Komplexitätstheorie gehts doch eben gerade um große N!?
Ist das so? Ich dachte, man spricht stets vom allgemeinen Fall.
Wenn wir von der Laufzeitkomplexität reden, dann reden wir vom asymptotischen Laufzeitverhalten. Die Notation mit Landau-Symbolen drückt genau das aus. Man beachte das "asymptotisch".
Aber es gibt asymptotisches Laufzeitverhalten für Best, Worst und Average Case. Und noch mehr, wie amortisierte Laufzeit. "asymptotisch" macht noch nicht automatisch average.
-
volkard schrieb:
dot schrieb:
314159265358979 schrieb:
dot schrieb:
Dann nehmen wir eben Mergesort oder Heapsort und schon ist der Worst-Case signifikant besser.
Dann wird dein Algorithmus erst recht verlieren :p
Nö wieso, ich hab doch ne bessere Laufzeitkomplexität!?
Noch sehe ich nicht, wie er funktioniert.
Die Laufzeitkomplexität meines Algorithmus entspricht dem des verwendeten Sortierverfahrens, also je nachdem auf jeden Fall O(n*log n) im Average-Case. Wenn ich mir den Algorithmus im Anfangsposting anschau, seh ich doch mit freiem Auge, dass der da nicht rankommen wird.
Anyway, um das Klarzustellen: Mir ist bewusst, dass "mein" Algorithmus praktisch völliger Mist ist. Ich wollte PI so dazu provozieren, sich etwas genauer mit der Bedeutung der O-Notation auseinanderzusetzen, das ist alles. Aber ich muss zugeben, im Nachhinen betrachtet war das eine eher weniger produktive Aktion von mir, bitte daher um Entschuldigung.
volkard schrieb:
dot schrieb:
314159265358979 schrieb:
dot schrieb:
In der Komplexitätstheorie gehts doch eben gerade um große N!?
Ist das so? Ich dachte, man spricht stets vom allgemeinen Fall.
Wenn wir von der Laufzeitkomplexität reden, dann reden wir vom asymptotischen Laufzeitverhalten. Die Notation mit Landau-Symbolen drückt genau das aus. Man beachte das "asymptotisch".
Aber es gibt asymptotisches Laufzeitverhalten für Best, Worst und Average Case. Und noch mehr, wie amortisierte Laufzeit. "asymptotisch" macht noch nicht automatisch average.
Klar, aber siehe oben.
-
Oder ein Zeigerfeld auf das Hauptfeld nehmen und darauf sort(nach Pointee), unique(nach Pointee), sort(nach Pointer) machen und dann das Hauptfeld anhand der sortiert vorliegenden Zeiger kompaktifizieren.
-
*snip* ich geh besser schlafen ^^
-
Bei average muß man festlegen worüber man mittelt. Bei Quicksort zum Beispiel nimmt man gern alle beliebigen Anordnungen einer (festen) Eingabesequenz und mittelt über die. Das Veralten gilt dann sogar instanzweise. Bei dir spielen die Umordnungen allerdings keine Rolle, weil es nur auf die Anzahl der verschiedenen Elemente ankommt. Ist die klein, ist der Algo recht sparsam, danach wird's rapide teurer.
Mitteln über alle Instanzen hilft da auch nicht, weil in der überwiegenden Mehrheit aller Instanzen (wie volkard vorgeschlagen hat) alle Elemente verschieden sind bzw. Zumindest alle Elemente vorkommen.
Ohnehin hat schon die Fragestellung ob eine Sequenz zwei gleiche Elemente enthält eine lower bound von Ω(n log n), und das beantwortest du ja quasi nebenbei. Das von dot vorgeschlagene Verfahren ist also in diesem Sinne optimal, seine Laufzeit mit der unteren Schranke übereinstimmt.
-
Jester schrieb:
Das von dot vorgeschlagene Verfahren ist also in diesem Sinne optimal, seine Laufzeit mit der unteren Schranke übereinstimmt.
Entweder: Sein Worst-Case-Verhalten ist optimal.
Oder: Unter der Annahme, daß nur Vergleiche benutzt werden dürfen.Man kann statt der map gerne eine hashtable nehmen und kommt dann auf ein Worst-Case-Verhalten von O(n²) aber erkauft sich dabei ein Average-Case-Verhalten von O(n).
Jester schrieb:
Mitteln über alle Instanzen hilft da auch nicht, weil in der überwiegenden Mehrheit aller Instanzen (wie volkard vorgeschlagen hat) alle Elemente verschieden sind bzw. Zumindest alle Elemente vorkommen.
Ab 77164 zufälligen ints gehe ich davon aus, daß nicht alle Elemente verschieden sind und noch längst nicht alle möglichen Elemente vorkommen. Aber stimmt schon, wenn man n gegen unendlich laufen läßt, aber der int 32-bittig bleibt, kommen vermutlich alle möglichen ints mal vor.
-
volkard schrieb:
Aber stimmt schon, wenn man n gegen unendlich laufen läßt, aber der int 32-bittig bleibt, kommen vermutlich alle möglichen ints mal vor.
Von 32-bittigen ints darfst du nicht ausgehen. Ansonsten geh ich alle Werte von -2^31 bis 2^31 - 1 durch und lösche alle bis auf das erste Vorkommen. Damit habe ich Laufzeit O(n) :p
-
314159265358979 schrieb:
Der best case wäre, wenn alle Elemente gleich sind. Dann wird std::remove lediglich einmal aufgerufen. Im Worst case, wenn alle Elemente verschieden sind, wird std::remove n mal aufgerufen. Und std::remove hat immer O(n)
Oh, natürlich. Es war schon spät.
-
Michael E. schrieb:
volkard schrieb:
Aber stimmt schon, wenn man n gegen unendlich laufen läßt, aber der int 32-bittig bleibt, kommen vermutlich alle möglichen ints mal vor.
Von 32-bittigen ints darfst du nicht ausgehen. Ansonsten geh ich alle Werte von -2^31 bis 2^31 - 1 durch und lösche alle bis auf das erste Vorkommen. Damit habe ich Laufzeit O(n) :p
Jup. Sogar der Algo des ersten Postings hat dann auch om Worst Case O(n), weil er nach spätestens 2^32 mal std::remove aufrufen fertig ist.
-
Fixe Idee meines Profs: Lege eine Hashtabelle an. Prüfe für jede Zahl, ob sie bereits in der Hashtabelle liegt. Fall nein, füge sie ans Ergebnis an. Damit sollte man eine lineare erwartete Laufzeit erhalten.
-
Mit Hashtabellen ist das immer so 'ne Sache: Hat die zu Grunde liegende hash-Funktion nicht die gewünschten Eigenschaften, dann gehen alle nicht worst case Analysen den Bach runter. Es ist wesentlich einfacher eine gute Vergleichsfunktion zu schreiben, als eine gute Hashfunktion.
Um auf das Ausgangsposting zurück zu kommen: Die Frage ist unter spezifiziert. Um über Average Case reden zu können braucht man eine Eingabeverteilung, sonst ist gar nicht klar welche Instanzen häufig sind und welche nicht. "Gleichverteilt" reicht da meistens nicht aus. Zum Beispiel ist "1 2" eine andere Instanz als "1 3"? Es sind andere Zahlen, aber wenn man sich nur die Ergebnisse der Vergleichsfunktion anschaut, dann sind es die selben Instanzen.
Hin und wieder kann man sich um die Definition der Eingabeverteilung rummogeln indem man die Eingabe einfach zufällig durcheinander wirbelt und dadurch eine gewisse Verteilung erzwingt. Ich sehe aber nicht, wie das hier gehen sollte.
