Komplexitätstheorie - Average Case Laufzeit eines Algortihmus

314159265358979

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)

volkard

314159265358979 schrieb:

Ich hoffe es ist okay, wenn ich hier C++-Code poste, ich tue mir schwer, das in Worte zu fassen

Netter wäre C. Oder pascaloider Pseudocode.
Ein Leser muß nicht wissen, was std::remove alles machte und wie lange es braucht. So, wie der Code da steht, empfinde ich es als unhöflich.

314159265358979

Okay, hier nochmal in C (hoffe ich jedenfalls, ich kann nichts aus C++ entdecken):

int* remove(int* begin, int* end, int value)
{
	int* curr = begin;

	for(; begin != end; ++begin)
		if(*begin != value)
			*curr++ = *begin;

	return curr;
}

int* unique_sorted(int* begin, int* end)
{
	for(; begin != end; ++begin)
		end = remove(begin + 1, end, *begin);

	return end;
}

Beide Funktionen verändern die Größe einer Sequenz nicht, sie schieben lediglich "gewollte" Elemente vor und geben danach einen Zeiger auf das erste ungewollte Element zurück (bzw hinter das letzte gewollte).

dot

http://www.cplusplus.com/reference/algorithm/unique/

314159265358979

std::unique entfernt aber nur Duplikate, die hintereinander liegen

dot

Darum sortiert man eben zuerst...

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