Komplexitätstheorie - Average Case Laufzeit eines Algortihmus

314159265358979

Ich wills aber stabil haben :p

dot

Dann kopier eben rum, das geht alles in O(n), hat also keinen Einfluss auf die Laufzeitkomplexität...

314159265358979

Mit "Dann kopier eben rum" fange ich leider nicht viel an, kannst du mir bitte genauer erklären, was du meinst?

Und trotzdem interessiert mich das ursprüngliche Problem, es geht nicht darum einen super-tollen Algorithmus zu finden, sondern darum, wie ich die Average-Case Komplexität hier bestimmen kann.

dot

314159265358979 schrieb:

Mit "Dann kopier eben rum" fange ich leider nicht viel an, kannst du mir bitte genauer erklären, was du meinst?

Ja kopier deinen Container eben, sortier die Kopie, und entfern dann die Duplikate. Rein von der Komplexität her ist das deutlich günstiger als dein Algorithmus :p

314159265358979 schrieb:

Und trotzdem interessiert mich das ursprüngliche Problem, es geht nicht darum einen super-tollen Algorithmus zu finden, sondern darum, wie ich die Average-Case Komplexität hier bestimmen kann.

Um die Laufzeitkomplexität im Average-Case bestimmen zu können, musst du erstmal definieren, was dein Average-Case ist.

314159265358979

dot schrieb:

Ja kopier deinen Container eben, sortier die Kopie, und entfern dann die Duplikate. Rein von der Komplexität her ist das deutlich günstiger als dein Algorithmus :p

Wenn man von nem Quicksort ausgeht, haben mein Algorithmus und Quicksort die selbe Komplexität im Best+Worst Case. Hinzu kommen Kosten fürs Kopieren sowie die Kosten des entfernens von Duplikaten (wobei ich gerade nicht weiß, wie du dir das vorstellst.) Möglicherweise ist dein Algo bei sehr großen N flotter, aber meiner gewinnt bei kleinen N ziemlich sicher.

dot schrieb:

Um die Laufzeitkomplexität im Average-Case bestimmen zu können, musst du erstmal definieren, was dein Average-Case ist.

Genau da liegt ja das Problem - Ich habe keine Idee, wie man einen Average Case definieren könnte. Irgendwas zwischen "Alle Elemente sind gleich" und "Alle Elemente sind verschieden".

dot

314159265358979 schrieb:

Wenn man von nem Quicksort ausgeht, haben mein Algorithmus und Quicksort die selbe Komplexität im Best+Worst Case.

Dann nehmen wir eben Mergesort oder Heapsort und schon ist der Worst-Case signifikant besser. Nehmen wir Timsort, so bekommen wir sogar besseren Worst-Case ohne den idealen Best-Case einzubüßen.

314159265358979 schrieb:

Hinzu kommen Kosten fürs Kopieren sowie die Kosten des entfernens von Duplikaten

Die Komplexität des restlichen Algorithmus übersteigt die des Kopierens, daher fällt das weg.

314159265358979 schrieb:

Algo bei sehr großen N flotter, aber meiner gewinnt bei kleinen N ziemlich sicher.

In der Komplexitätstheorie gehts doch eben gerade um große N!?

314159265358979 schrieb:

dot schrieb:

Um die Laufzeitkomplexität im Average-Case bestimmen zu können, musst du erstmal definieren, was dein Average-Case ist.

Genau da liegt ja das Problem - Ich habe keine Idee, wie man einen Average Case definieren könnte. Irgendwas zwischen "Alle Elemente sind gleich" und "Alle Elemente sind verschieden".

Ja. Du wirst eben eine durchschnittliche Verteilung annehmen und dann den Erwartungswert der Laufzeitkomplexität deines Algorithmus bei gegebener Verteilung berechnen müssen.

314159265358979

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

dot schrieb:

Die Komplexität des restlichen Algorithmus übersteigt die des Kopierens, daher fällt das weg.

Da hast du zwar Recht, aber ich wollte nur daran erinnern, dass kopieren nicht gratis ist.

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.

dot schrieb:

Ja. Du wirst eben eine durchschnittliche Verteilung annehmen und dann den Erwartungswert der Laufzeitkomplexität deines Algorithmus bei gegebener Verteilung berechnen müssen.

Ich kann dir zwar folgen, aber wie man sich das damit ausrechnen kann, weiß ich damit immer noch nicht.

volkard

314159265358979 schrieb:

Ich wills aber stabil haben :p

int* unique_sorted(int* begin, int* end)//n sei die Anzahl der Elemente
{
    set<int> schonGesehen;//Die Methoden has und insert kosten O(log(m)), wobei m die Anzahl der Elemente in der Set ist. 
    int* writePos=begin;
    for(int* readPos=begin ; readPos!=end; ++readPos)//läuft n mal
    {
       if(not schonGesehen.has(*readPos))//kostet O(log(m))
       {
          schonGesehen.insert(*readPos);//macht den Bocj nicht mehr fett
          *writePos=*readPos;
       }
    }
    return writePos;
}

macht O(n*log(m)), wobei n die Anzahl der Elemente ist und m die Anzahl der unterschiedlichen Werte.

volkard

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.

314159265358979

volkard schrieb:

...
macht O(n*log(m)), wobei n die Anzahl der Elemente ist und m die Anzahl der unterschiedlichen Werte.

An ein set habe ich auch schon gedacht, jedoch aufgrund des Extra-Speichers erstmal verzichtet.

volkard schrieb:

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.

Jop, das meinte ich

volkard

314159265358979 schrieb:

sondern darum, wie ich die Average-Case Komplexität hier bestimmen kann.

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.

dot

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!?

314159265358979 schrieb:

dot schrieb:

Die Komplexität des restlichen Algorithmus übersteigt die des Kopierens, daher fällt das weg.

Da hast du zwar Recht, aber ich wollte nur daran erinnern, dass kopieren nicht gratis ist.

Da hast du zwar recht, aber für die Laufzeitkomplexität spielt das keine Rolle.

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

dot

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

314159265358979

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"?

dot

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

volkard

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.

dot

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.

volkard

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.

dot

*snip* ich geh besser schlafen ^^

Jester

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.