Komplexitätsklassen

[Gregor]

freakC++ schrieb:

Das ist klar. Trotzdem kann man ja den worst case und den best case einer Klasse so allgemein beschreiben. Damit ist zum Beispiel klar, dass ein Problem niemals in logarithmischer Zeit lösbar ist.

Best Case macht da nur wenig Sinn, denn mit den Komplexitätsklassen sieht es ungefähr so aus (ich beschränke mich hier auf nur ein paar und lasse ungefähr 100 weg):

$\text{L} \subseteq \text{NL} \subseteq \text{P} \subseteq \text{NP} \subseteq \text{PSPACE} \subseteq \text{EXP} \subseteq \text{NEXP}$

Das heißt, zwischen den einzelnenen Komplexitätesklassen bestehen Teilmengen-Beziehungen. Bei einigen weiß man auch, dass die Mengen nicht gleich sein können, zum Beispiel ist P eine echte Teilmenge von EXP. Aber es macht dann keinen Sinn, von einem Best Case für eine Klasse zu reden: Jedes Problem in NL ist auch in P.

[freakC++]

Dann werde ich nicht mehr von einem worst- oder best-case einer Klasse reden. Ich soll aber über die "Komplexitätsklassen POLY und NPOLY" bescheid wissen.

Vielleicht stelle ich mich auf nur doof an, aber was sind das für Klassen. Ich kenne L, NL, P, NP, EXPTIME, NEXPTIME, EXPSPACE, NEXPSPACE. Was ist aber POLY?

Danke
lg, freakC++

[ipsec]

Vom Namen her würde ich denken, es sind P und NP gemeint.

[freakC++]

Das würde Sinn machen. Dann hoffe ich einfach mal, dass das richtig ist.

Ich habe noch eine andere Frage. Im Unterricht sagten wir, dass die Lineare Suche in die Komplexitätsklasse P gehöre. Ich weiße, dass die Unterschranke von P der Logarithmus ist und die Oberschranke ein Polynom. Bei der Linearen Suche ist es aber so, dass das gesucht Element gleich am Anfang liegt. Der best-case wäre also Omeaga(1). Das würde aber nur zur Komplexitätsklasse L passen. Was ist jetzt richtig?

Ich danke euch
lg, freakC++

[CStoll]

Um die Laufzeit eines Algorithmus einstufen zu können, darfst du nicht nur den optimalsten Fall betrachten, sondern alle möglichen Eingaben (im besten Fall ist BubbleSort auch schneller als QuickSort).

PS: Außerdem geht es bei L um den Platzbedarf - und ja, die lineare Suche dürfte imho auch in L liegen (sie braucht außer der Eingabe nur konstanten Speicherplatz).

[freakC++]

CStoll schrieb:

(sie braucht außer der Eingabe nur konstanten Speicherplatz).

Das bedeutet nur, dass der Algorithmus inplace arbeitet, aber sollte sich nicht auf die Komplexität auswirken.

CStoll schrieb:

Um die Laufzeit eines Algorithmus einstufen zu können, darfst du nicht nur den optimalsten Fall betrachten

Ich dachte, in diesem Fall ist es egal, weil wenn der optimalste Fall 1 ist, dann kann der Algorithmus gar nicht in P liegen, weil solche Probleme in L sind. Oder?

CStoll schrieb:

(im besten Fall ist BubbleSort auch schneller als QuickSort).

Stimmt! Trotzdem liegen beide in P, oder?

lg, freakC++

[Michael E.]

freakC++ schrieb:

Im Unterricht sagten wir, dass die Lineare Suche in die Komplexitätsklasse P gehöre.

Das ist korrekt. Wähle als Polynom p(x) = x.

Ich weiße, dass die Unterschranke von P der Logarithmus ist

Wer sagt denn sowas? Was soll überhaupt eine Schranke für eine Unterschranke sein? Auch Σ* liegt in P, obwohl es Algorithmen für diese Sprache mit Worst-Case-Laufzeit O(1) gibt (einfach immer sofort akzeptieren).

und die Oberschranke ein Polynom.

Auch hier wieder: Was soll eine Oberschranke für eine Klasse sein?

Selbst wenn man deine Aussage etwas anders interpretiert (so wie du sie wahrscheinlich gemeint hast), ist sie immer noch falsch: Es gibt kein Polynom p, sodass P = O(p).

Bei der Linearen Suche ist es aber so, dass das gesucht Element gleich am Anfang liegt. Der best-case wäre also Omeaga(1).

Best Cases interessieren hier nicht.

[freakC++]

Wenn ich einen Algorithmus habe und entscheiden möchte, in welcher Komplexitätsklasse er gehört, dann tue ich das anhand der Ober- und Untergrenze (O- und Omega-Notation). Wahrscheinlich ist das falsch, denn stoße dabei ja auf Widerstand. Ich dachte, dass die Lineare Suche eine Untergrenze (Omega) von 1 hat und daher in L gehört, weil wir uns das so aufgeschrieben haben. P kann bestensfalls logarithmisch sein. Das hatten wir uns ebenfalls aufgeschrieben.

Ist die Lineare Suche jetzt in P oder L. Ich bin weiterhin für L.

[CStoll]

freakC++ schrieb:

CStoll schrieb:

(sie braucht außer der Eingabe nur konstanten Speicherplatz).

Das bedeutet nur, dass der Algorithmus inplace arbeitet, aber sollte sich nicht auf die Komplexität auswirken.

Die Komplexitätsklasse L ist definiert über den Platzverbrauch (und mit der Bedingung, daß die Eingabe nicht überschrieben wird - darum sind auch InPlace-Sortieralgorithmen nicht in L).

CStoll schrieb:

Um die Laufzeit eines Algorithmus einstufen zu können, darfst du nicht nur den optimalsten Fall betrachten

Ich dachte, in diesem Fall ist es egal, weil wenn der optimalste Fall 1 ist, dann kann der Algorithmus gar nicht in P liegen, weil solche Probleme in L sind. Oder?

Erstens: Für die Laufzeit darfst du nicht nur die "guten" Eingaben betrachten, sondern ALLE möglichen Eingaben.
Zweitens: Wo ist hier der Widerspruch? L ist eine Teilmenge von P, damit liegt natürlich auch jedes L-Problem in den höheren Komplexitätsklassen.

CStoll schrieb:

(im besten Fall ist BubbleSort auch schneller als QuickSort).

Stimmt! Trotzdem liegen beide in P, oder?

Das auch - aber darauf wollte ich nicht hinaus.
Bei den Sortieralgorithmen geht es schon gar nicht um die Frage, ob sie nun polynomiell sind. In dem Bereich geht es schon um den Exponenten des Polynoms.

Im besten Fall hat BubbleSort eine Laufzeit von O(n) und QuickSort O(n log n), im schlechtesten Fall kommen beide auf O(n²). Für die allgemeine Betrachtung verwendet man aber meistens den durchschnittlichen Fall (da kommen die beiden Algorithmen auf O(n²) bzw O(n log n)), gelegentlich wird auch der worst-case oder die Proportionalitätskonstante hinter dem O() wichtig.
(btw, die besten und schlechtesten Fälle unterscheiden sich je nach Algorithmus ;))

[Michael E.]

freakC++ schrieb:

Wenn ich einen Algorithmus habe und entscheiden möchte, in welcher Komplexitätsklasse er gehört, dann tue ich das anhand der Ober- und Untergrenze (O- und Omega-Notation).

Der Algorithmus liegt nicht in den Komplexitätsklassen, sondern das Problem, welches er löst. Außerdem hast du von Ober- und Untergrenzen für Klassen und nicht für Algorithmen gesprochen. Desweiteren ist nur die Obergrenze interessant.

Ich dachte, dass die Lineare Suche eine Untergrenze (Omega) von 1 hat und daher in L gehört, weil wir uns das so aufgeschrieben haben. P kann bestensfalls logarithmisch sein. Das hatten wir uns ebenfalls aufgeschrieben.

Dann habt ihr euch was Falsches aufgeschrieben. Vielleicht meinst du P \ L oder etwas dergleichen.

Ist die Lineare Suche jetzt in P oder L. Ich bin weiterhin für L.

In beiden.