Komplexitätstheorie, O-Notation

08.11.2022, 14:49

Malcang

Komplexitätstheorie, O-Notation

Hallo zusammen,

mir fällt immernoch die Interpretation der Schreibweisen $\begin{eqnarray*} \mathcal{O}(n), \Omega(n) \end{eqnarray*}$ etc... sehr schwer.
Ich habe mir nun ein Buch über Komplexitätstheorie genommen (Wegener, Komplexitätstheorie). Dort findet sich beispielweise:

Zitat:

Wenn wir auf Bitebene absteigen, braucht jede arithmetische Operation auf Zahlen der Bitlänge $\begin{eqnarray*} l \end{eqnarray*}$ sicher $\begin{eqnarray*} \Omega(l) \end{eqnarray*}$ Operationen. Für Additionen und Subtraktionen genügen auch $\begin{eqnarray*} \mathcal{O}(l) \end{eqnarray*}$ Operationen, während die besten bekannten Algorithmen für Multiplikation und Division $\begin{eqnarray*} \Theta(l\log(l)\log(\log(l)) \end{eqnarray*}$ Operationen benötigen.

Die Notationen sind im Anhang auch erklärt wie ich es kenne, aber die Interpretation fällt mir schwer.

Nehmen wir

Zitat:

Wenn wir auf Bitebene absteigen, braucht jede arithmetische Operation auf Zahlen der Bitlänge $\begin{eqnarray*} l \end{eqnarray*}$ sicher $\begin{eqnarray*} \Omega(l) \end{eqnarray*}$

.

Kann ich das lesen als: "Nehme ich eine Zahl, die aus $\begin{eqnarray*} l \end{eqnarray*}$ Bits besteht, so benötige ich für jede arithmetische Operationen nicht weniger als $\begin{eqnarray*} l \end{eqnarray*}$ Operationen?" verwirrt

08.11.2022, 15:00

HAL 9000

Auf diesen Beitrag antworten »

Nein, dieses Landau-Symbol beinhaltet auch noch einen Faktor, d.h. es gibt ein $\begin{eqnarray*} c>0 \end{eqnarray*}$ , so dass man mindestens $\begin{eqnarray*} c\cdot l \end{eqnarray*}$ Operationen benötigt. $\begin{eqnarray*} \Omega(l) \end{eqnarray*}$ allein sagt nichts darüber aus, wie groß dieses $\begin{eqnarray*} c \end{eqnarray*}$ ist - es kann also durchaus auch $\begin{eqnarray*} 0<c<1 \end{eqnarray*}$ sein.

Zitat:

Original von Malcang
während die besten bekannten Algorithmen für Multiplikation und Division $\begin{eqnarray*} \Theta(l\log(l)\log(\log(l)) \end{eqnarray*}$ Operationen benötigen.

Und das ist schon bemerkenswert! Denn mit dem naiven Multiplikationsalgorithmus (wie man ihn vom schriftlichen Multiplizieren kennt, nur eben auf Bitebene) ist man nämlich beim viel größeren $\begin{eqnarray*} \Theta(l^2) \end{eqnarray*}$ . Worauf hier bezogen wird, sind vermutlich die auf FFT basierenden Algorithmen.

08.11.2022, 15:27

Malcang

Auf diesen Beitrag antworten »

Hallo HAL 9000,

danke für deinen Beitrag.
Dieser Faktor $\begin{eqnarray*} c \end{eqnarray*}$ ist aber dann für jede Eingabe gültig, unabhängig von der Anzahl der Bitstellen $\begin{eqnarray*} l \end{eqnarray*}$ , richtig?

Und das habe ich ja dann auch bei Additionen und Subtraktionen zu beachten:

Zitat:

Für Additionen und Subtraktionen genügen auch $\begin{eqnarray*} \mathcal{O}(l) \end{eqnarray*}$ Operationen

bedeutet also:
"Wenn meine Eingabe $\begin{eqnarray*} n \end{eqnarray*}$ in Bits genau $\begin{eqnarray*} l \end{eqnarray*}$ Stellen belegt, dann brauche ich für Addition und Subtraktion jeweils nicht mehr als $\begin{eqnarray*} c\cdot l \end{eqnarray*}$ Operationen, wobei $\begin{eqnarray*} c > 0 \end{eqnarray*}$ gilt."?

Zitat:

Denn mit dem naiven Multiplikationsalgorithmus (wie man ihn vom schriftlichen Multiplizieren kennt, nur eben auf Bitebene) ist man nämlich beim viel größeren $\begin{eqnarray*} \Theta(l^2) \end{eqnarray*}$ .

Das ist ein gutes Beispiel. Ich habe zwei Zahlen in Bitdarstellung. Sagen wir, die erste Zahl hat $\begin{eqnarray*} l_1 \end{eqnarray*}$ Bitstellen, die zweite Zahl $\begin{eqnarray*} l_2. \end{eqnarray*}$ Multipliziere ich schriftlich, muss ich $\begin{eqnarray*} l_1\cdot l_2 \end{eqnarray*}$ mal multiplizieren.
Das Aufsummieren der Werte betrachte ich für die Komplexität nicht mehr, weil Multiplizieren ohnehin aufwändiger ist als Addieren?

Und $\begin{eqnarray*} \Theta(l^2) \end{eqnarray*}$ bedeutet doch, dass ich nicht weniger als $\begin{eqnarray*} c_1\cdot \max\left\{ l_1, l_2 \right\} \end{eqnarray*}$ Operationen benötige, aber nicht mehr mehr als $\begin{eqnarray*} c_2\cdot \max\left\{ l_1, l_2 \right\} \end{eqnarray*}$ , oder?

08.11.2022, 16:30

HAL 9000

Auf diesen Beitrag antworten »

Bei verschiedenen Bitlängen $\begin{eqnarray*} l_1 \end{eqnarray*}$ und $\begin{eqnarray*} l_2 \end{eqnarray*}$ hat der naive Algorithmus die Komplexität $\begin{eqnarray*} \Theta(l_1\cdot l_2) \end{eqnarray*}$ statt $\begin{eqnarray*} \Theta(\max\{l_1,l_2\}) \end{eqnarray*}$ .

08.11.2022, 17:15

Malcang

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Bei verschiedenen Bitlängen $\begin{eqnarray*} l_1 \end{eqnarray*}$ und $\begin{eqnarray*} l_2 \end{eqnarray*}$ hat der naive Algorithmus die Komplexität $\begin{eqnarray*} \Theta(l_1\cdot l_2) \end{eqnarray*}$ statt $\begin{eqnarray*} \Theta(\max\{l_1,l_2\}) \end{eqnarray*}$ .

Ach ja, natürlich Hammer

Meine Interpretation würde ja nun lauten "Ich brauche nicht weniger als $\begin{eqnarray*} c_1\cdot l_1\cdot l_2 \end{eqnarray*}$ Operationen, aber nicht mehr als $\begin{eqnarray*} c_2\cdot l_1\cdot l_2 \end{eqnarray*}$ ".
Aber die Komplexität betrifft ja den asymptotischen Fall. Wenn ich jetzt die Konstanten kennen würde, sagen wir $\begin{eqnarray*} c_1 = 2, c_2 = 5 \end{eqnarray*}$ , dann könnte es doch trotzdem sein, das für hinreichend kleine $\begin{eqnarray*} l_1, l_2 \end{eqnarray*}$ die Anzahl der Operationen möglicherweise $\begin{eqnarray*} 10\cdot l_1 \cdot l_2 \end{eqnarray*}$ ist, oder nicht? (Nicht im Beispiel der schriftlichen Multiplikation, sondern im Allgemeinen Fall eines Algorithmus mit Komplexität $\begin{eqnarray*} \Theta(l_1\cdot l_2) \end{eqnarray*}$ ).

Neue Frage »

Antworten »

Komplexitätstheorie, O-Notation

Verwandte Themen