komplexitätsmessung

[tsag (Gast)]

Hallo,

ich bin gerade dabei Optimierungspotential bei einem Algorithmus zu 
suchen. Dafür habe ich die einzelnen Funktionen mit verschiedenen 
Datenlängen aufgerufen und mit einem Timer die Taktzyklen gemessen. 
Innerhalb meines Algorithmus gibt es Sortieralgorithmen, wie Bubblesort, 
welcher ja bekanntlich O(n^2) ist. Die Datenmenge die sortiert wird ist 
aber unabhängig von meinen Datenlängen, da nur konstant lange Ausschntte 
sortiert werden müssen. Daher meine Frage: Ist es (wissenschaftlich) 
korrekt, wenn ich jeden Verarbeitungsschritt, wie soeben beschrieben 
untersuce und anschlieend aus den gewonnenden Daten eine Funktion in der 
Form 20*n^2 + 40 * n + 30 aufstellen und der Sortierteil ist darin eine 
Konstante, weil ich ja eine feste Datenmenge sortiere oder wie macht man 
soetwas?

Gruß

[Programmierer (Gast)]

Konstante Zeiten sind für die Komplexitätsmessung völlig irrelevant. 
Nimm es einfach als 0 an.

[Johann L. (gjlayde)]

tsag schrieb:
> Hallo,
>
> [...] und der Sortierteil ist darin eine Konstante, weil ich ja
> eine feste Datenmenge sortiere [...]

Fest wird die Datenmenge wohl nicht sein, sondern nur ihre Größe 
(Mächtigkeit)?

Neben der Anzahl der zu sortierenden Elemente gehen noch andere Faktoren 
in die Komplexität ein wie:

1) Kosten zum Kopieren / Verschieben der Elemente.  Kopieren von 
Objekten wie z.B. Zeichenketten ist i.d.R teurer als Zeiger darauf zu 
sortieren.  Ein Verzeichnis mit 10 Datei-Einträgen zu sortieren ist 
billiger, als die entsprechenden Dateien auf Platte sortiert anzuordnen. 
Bei Neuanordnung der Dateien auf Platte geht die (maximale) Größe der 
Dateien in die Komplexität ein.

2) Kosten zur Bestimmung der Ordnungsrelation: Falls diese nicht als 
konstant angenommen weden können, gehen sie ebenfalls in die Komplexität 
ein.  Beispiel: Es sollen natürliche Zahlen sortiert werden, und das 
Sortierkriterium ist die Anzahl der Primfaktoren.  Auch wenn immer nur 
10 Zahlen zu sortieren sind, ist die Komplexität stark abhängig von der 
(maximalen) Größe der Zahlen.

Falls eine von den Daten unabhängige obere Grenze existiert, die die 
Komplexität natürlich konstant — egal wie groß die Grenze ist.

[Programmierer (Gast)]

Johann L. schrieb:
> 1) Kosten zum Kopieren / Verschieben der Elemente.  Kopieren von
> Objekten wie z.B. Zeichenketten ist i.d.R teurer als Zeiger darauf zu
> sortieren.
Das ist aber irrelevant für die Komplexität und Angabe in 
Landau-Symbolen, da Konstanten und Faktoren ignoriert werden.

Johann L. schrieb:
> Falls eine von den Daten unabhängige obere Grenze existiert, die die
> Komplexität natürlich konstant — egal wie groß die Grenze ist.
Die Komplexität ist dann O(1), egal wie groß die Grenze ist

[Johann L. (gjlayde)]

Programmierer schrieb:
> Johann L. schrieb:
>> 1) Kosten zum Kopieren / Verschieben der Elemente.  Kopieren von
>> Objekten wie z.B. Zeichenketten ist i.d.R teurer als Zeiger darauf zu
>> sortieren.
> Das ist aber irrelevant für die Komplexität und Angabe in
> Landau-Symbolen, da Konstanten und Faktoren ignoriert werden.

Nein, wenn ich dir 10 Zeichenketten zum Sortieren vorlege, und ich dir 
nicht sage, wie lang diese sind, kannst du die von dir benötigte Zeit 
nicht nach oben durch eine Konstante anschätzen.

Ditto für die Komplexität von Vergleichen. Wie lange benötogst du, um 2 
Zahlen nach o.g. Regel zu vergleichen, denn ich dir keine Obergranze 
für die Tahlen sage / sagen kann?

In Komplexitätsbetrachtungen gehen nicht nur die Anzahl von Daten ein, 
sondern auch andere Eigenschaften. I.d.R sind Berechnungen, erlche diese 
anderen Eigenschaften verwenden O(1), etwa weil nur mit 64-Bit Zahlen 
hantiert wird.  In einem CA System ist das zum Beispiel nicht mehr der 
Fall.

Bei vielen Objekten aus der Algebra sind vergleiche extrem teuer und 
haben nicht Komplexität O(1).  Beispiel: Du sortierst 2 Zahlenkörper 
nach deren Klassenzahl.


> Johann L. schrieb:
>> Falls eine von den Daten unabhängige obere Grenze existiert, ist
>> die Komplexität natürlich konstant — egal wie groß die Grenze ist.
> Die Komplexität ist dann O(1), egal wie groß die Grenze ist.

[Karl H. (kbuchegg)]

Johann L. schrieb:
> Programmierer schrieb:
>> Johann L. schrieb:
>>> 1) Kosten zum Kopieren / Verschieben der Elemente.  Kopieren von
>>> Objekten wie z.B. Zeichenketten ist i.d.R teurer als Zeiger darauf zu
>>> sortieren.
>> Das ist aber irrelevant für die Komplexität und Angabe in
>> Landau-Symbolen, da Konstanten und Faktoren ignoriert werden.
>
> Nein, wenn ich dir 10 Zeichenketten zum Sortieren vorlege, und ich dir
> nicht sage, wie lang diese sind, kannst du die von dir benötigte Zeit
> nicht nach oben durch eine Konstante anschätzen.

Bei der O Notation geht es nicht um konkrete Zeiten, sondern darum mit 
welcher Tendenz der Zeitbedarf mit wachsendem n zunimmt.
Bei einem Polygon ist es der Term mit dem höchsten Exponenten, der die 
generelle Tendenz bestimmt.

Ob bei einer quadratischen Funktion die Parabel entlang der y-Achse 
verschoben ist oder nicht, ist in der O-Notation uninteressant. Wichtig 
ist, dass es eine Parabel ist und ein doppelt so hohes n in etwa die 
4-fache Laufzeit benötigen wird. Was immer auch diese Laufzeit in einer 
konkreten Implementierung ist.

[Johann L. (gjlayde)]

Karl Heinz schrieb:
> Ob bei einer quadratischen Funktion die Parabel entlang der y-Achse
> verschoben ist oder nicht, ist in der O-Notation uninteressant.

Das ist ja alles klar.

> Johann L. schrieb:
>> Nein, wenn ich dir 10 Zeichenketten zum Sortieren vorlege, und ich dir
>> nicht sage, wie lang diese sind, kannst du die von dir benötigte Zeit
>> nicht nach oben durch eine Konstante anschätzen.
>
> Bei der O Notation geht es nicht um konkrete Zeiten, sondern darum mit
> welcher Tendenz der Zeitbedarf mit wachsendem n zunimmt.

D.h. man geht (implizit) davon aus, die Komplexität sei nur von der 
Anzahl der — in diesem Fale zu sortierenden — Objekte abhängig?

Frage: Was ist die Zeitkomplexität zum Sortieren von n Strings der Länge 
n mit Bubblesort. So wie ich dich verstehe wäre diese O(n^2), meine 
Intuition sagt aber O(n^3).  Was ist korrekt?

[Yalu X. (yalu) (Moderator)]

Johann L. schrieb:
> D.h. man geht (implizit) davon aus, die Komplexität sei nur von der
> Anzahl der — in diesem Fale zu sortierenden — Objekte abhängig?

Nein, die Komplexität kann durchaus von mehreren Größen abhängen.

> Frage: Was ist die Zeitkomplexität zum Sortieren von n Strings der Länge
> n mit Bubblesort. So wie ich dich verstehe wäre diese O(n^2), meine
> Intuition sagt aber O(n^3).  Was ist korrekt?

Du hast schon recht: Wenn man davon ausgeht, dass der Vergleich zweier
Strings der Länge k in O(k) geht, geht die gesamte Sortierung in O(n²·k)
bzw. für k=n in O(n³).

Ich glaube, Karl Heinz hat dich da einfach nur missverstanden.


Kleine Anmerkung am Rande:

O(k) ist die Komplexität des Stringvergleichs im schlechtesten Fall
(wenn die beiden Strings höchstens im letzten Zeichen unterscheiden).
Betrachtet man stattdessen die mittlere Laufzeit, reduziert sich die
Komplexität auf O(1), denn die zu erwartende Anzahl von Vergleichen
auf Zeichenebene ist

$$E=\frac a{a-1}\Big(1-\frac 1{a^k}\Big)$$

Dabei ist a die Alphabetgröße und k die Stringlänge. Dieser Ausdruck
konvergiert für k→∞ von unten gegen a/(a-1) ≤ 2.

[Lernender (Gast)]

Yalu X. schrieb:
> O(k) ist die Komplexität des Stringvergleichs im schlechtesten Fall
> (wenn die beiden Strings höchstens im letzten Zeichen unterscheiden).

Hallo Yalu X.,
das ist etwas unglücklich formuliert. Auch wenn sich die Strings 
allesamt im Vorletzten oder im 1/10*kten Zeichen unterschieden, wäre die 
Laufzeit O(k).

Nebenbei: Könntest du mir die Herleitung deiner Formel erläutern? :)

[Yalu X. (yalu) (Moderator)]

Lernender schrieb:
> das ist etwas unglücklich formuliert. Auch wenn sich die Strings
> allesamt im Vorletzten oder im 1/10*kten Zeichen unterschieden, wäre die
> Laufzeit O(k).

Ja, da hast du vollkommen recht.

> Nebenbei: Könntest du mir die Herleitung deiner Formel erläutern? :)

Die Wahrscheinlichkeit, dass das jweils i-te Zeichen der beiden Strings
gleich ist, ist

$$p_\mathrm g=\frac 1a$$

die Gegenwahrscheinlichkeit (also dass sie ungleich sind) ist

$$p_\mathrm u=\frac{a-1}a$$

Beim Vegleich der beiden String muss, von links beginnend, das erste
Zeichen gesucht werden, bei dem sie sich unterscheiden.

Die Wahrscheinlichkeit, dass man genau i Vergleiche braucht, um den
ersten Unterschied zu entdecken, ist für 1≤i<k

$$p_i=p_\mathrm g^{i-1}\cdot p_\mathrm u$$

Beim Vergleich des letzten Zeichens spielt dessen Ausgang keine Rolle,
da keine weiteren Vergleiche folgen. Daher ist die Wahrscheinlichkeit,
dass man k Vergleiche braucht,

$$p_k=p_\mathrm g^{k-1}$$

Zusammengefasst ist also

$$p_i=\begin{cases} \frac{a-1}{a^i} & \text{falls }1\leq i<k \\ \frac 1{a^{k-1}} & \text{falls }i=k \end{cases}$$

Der Erwartungswert für die Anzahl der erforderlichen Vergleiche ist

$$E_k=\sum_{i=1}^k p_i\cdot i=\sum_{i=1}^{k-1} \frac{(a-1)\cdot i}{a^i} + \frac k{a^{k-1}}$$

Die Summe kann man umschreiben als Summe einer geometrischen Reihe:

$$E_k=\sum_{j=1}^{k-1}\sum_{i=j}^{k-1} \frac {a-1}{a^i} + \frac k{a^{k-1}}$$

Ausrechnen der geometrischen Reihe ergibt

$$E_k=\sum_{j=1}^{k-1}\Big(\frac 1{a^{j-1}}-\frac 1{a^{k-1}}\Big) + \frac k{a^{k-1}} =\sum_{j=1}^{k-1}\frac 1{a^{j-1}} + \frac 1{a^{k-1}}$$

Die Summe stellt erneut eine geometrische Reihe dar, die ebenfalls
ausgerechnet wird:

$$E_k=\frac{a-\frac 1{a^{k-2}}}{a-1} + \frac 1{a^{k-1}} = \frac a{a-1}\Big(1-\frac 1{a^k}\Big)$$

Edit:

Ich sehe gerade, dass die Berechnung viel einfacher gegangen wäre:

Für Strings der Länge 1 braucht man immer genau einen Vergleich:

$$E_1=1$$

Erweitert man die Strings der Länge k jeweils um ein zusätzliches
Zeichen am Anfang, so muss man erst einmal diese beiden Zeichen
vergleichen (1 Vergleich). Nur wenn sie gleich sind (also mit der
Wahrscheinlichkeit 1/a), müssen die Reststrings ebenfalls verglichen
werden, was im Mittel E_k Vergleiche erfordert. Die zu erwartende Anzahl
Vergleiche für Strings der Länge k+1 ist somit

$$E_{k+1}=1+\frac 1a\cdot E_k$$

Diese rekursive Form für E_k sieht ausgeschrieben folgendermaßen aus:

$$E_k=1+\frac 1a+\frac 1{a^2}+\dots+\frac 1{a^{k-1}}=\sum_{i=0}^{k-1}\frac 1{a^i}$$

Das Ausrechnen dieser geometrischen Reihe führt zum o.g. Ergebnis.

[Karl H. (kbuchegg)]

Yalu X. schrieb:

>
> Ich glaube, Karl Heinz hat dich da einfach nur missverstanden.
>
>

Das könnte sein.

Bleiben wir beim Bubblesort (dem klassischen). Der hat Komplexität 
mindestens O(n quadrat). Keine noch so gute Verbesserung der 
Vergleichsfunktion wird daran etwas ändern. Doppelt so viele Daten, 
vierfache Laufzeit.
Habe ich aber ein Sortierverfahren mit O(n log(n)), dann kann die 
Vergleichsfunktion noch so mies sein, solange sie mir das O nicht 
übernimmt wird es immer ein n geben, so dass diese Sortierung schneller 
ist.
Meinem Verständnis nach ist dabei der genaue Wert von n gar nicht so 
massgeblich, weil er von vielen Faktoren abhängt. Eine ungefähre 
Vorstellung darüber, ob es klein oder gross ist, mag im Einzelfall 
hilfreich sein (Quicksort lohnt nicht bei kleinen Datenmengen). So wie 
ich das gelernt habe geht es mehr oder weniger um die Tatsache, das die 
Kurve für n*log(n) die Kurve für x_hoch_2 mit Sicherheit irgendwo im 
Endlichen schneidet, unabhängig davon, ob da noch Faktoren oder ein 
additiver Term dabei ist. Das ist (so hab ich das vor 30 Jahren mehr 
oder weniger gelernt) die Kernaussage, worum es bei der O Notation geht: 
um den Vergleich 2-er Algorithmen und wie sie mit wachsendem n 
skalieren, wenn n gegen unendlich geht

Vergleichen muss ich bei jedem Sortierverfahren. Die Frage ist nur: wie 
oft. N_quadrat mal oder n*log(n) mal.
(Bei einem Sortierverfahren können dann natürlich auch noch die 
Datenbewegungen eine Rolle spielen)

[Hans (Gast)]

Karl Heinz schrieb:
> Habe ich aber ein Sortierverfahren mit O(n log(n)), dann kann die
> Vergleichsfunktion noch so mies sein, solange sie mir das O nicht
> übernimmt wird es immer ein n geben, so dass diese Sortierung schneller
> ist.

Der Punkt war, dass die Dauer der Vergleichsfunktion theoretisch auch 
von n abhängen könnte. Zum Beispiel beim Fall "n Strings der Länge n". 
Sprich je mehr Strings sortiert werden, desto länger sind die einzelnen 
Strings bzw. desto länger dauert das Vergleichen zweier Strings.

Wenn man so einen Fall hat, muss man für die Gesamtkomplexität auch die 
Vergleichsfunktion mit einrechnen. Hier wäre es also O(n² log(n)).

Wenn die Vergleichsfunktion dagegen nur "mies" im Sinne von hohen 
"konstanten" Kosten (sprich unabhängig von der Anzahl der zu 
sortierenden Elemente) ist, überwiegt bei ausreichend großem n 
irgendwann der von n abhängige Teil der Gesamtkosten.