Frage zu Aufgaben: O-Notation, Komplexität

W0lf

Hallo,

ich bereite mich gerade auf eine anstehende Klausur vor und gehe hierfür ein paar Aufgaben durch.

Aufgabenstellung: Korrekte Aussagen mit Symbolen aus { $\in$ ,(durchgestrichenes) $\in$ , $\subseteq$ , (durchgestrichenes) $\subseteq$

Ich verstehe noch nicht ganz den Unterschied zwischen ist Teilmenge von und ist Element von.

Als Beispiel:

l(n) = 2²n
h(n) = 2^(n²+11)/1000

l(n)     [__]  O(h(n))

Ich würde jetzt ein tippen, dass da ein durchgestrichenes e reinmuss, aber wie gesagt, ich verstehe nicht ganz den Unterschied. Kann mir denn bitte gerade mal jemand erläutern?

Vielen Dank schonmal

zwutz

ich würd spontan ein durchgestrichenes $\subseteq$ nehmen, aber ich kann nur auf ein bisschen mengenlehre in der 5ten Klasse zurückblicken

Gregor

Etwas kann nur dann eine Teilmenge von etwas anderem sein, wenn es selbst eine Menge ist. Eine Funktion ist selbst keine Menge, die O(...) bezeichnen hingegen Mengen von Funktionen.

Jester

Ich würde auch ein durchgestrichenes Element-Zeichen reintun (wobei das eigentlich von der genauen Klammerung bei l(n) abhängt...

Wobei streng genommen auch ein durchgestrichenes Teilmengenzeichen nicht ganz falsch ist... immerhin ist l(n) ja keine Teilmenge. Allerdings könnte man das auch als Syntaxfehler werten, weil l(n) überhaupt keine Menge ist.

Exponentiation ist vereinbarungsgemäß rechtsassoziativ:

2²n := 2⁽²n)

Jester

u_ser-l schrieb:

Exponentiation ist vereinbarungsgemäß rechtsassoziativ:

2²n := 2⁽²n)

Dafür findet man bemerkenswert wenige Quellen. Wenn man bei google "exponentiation rechtsassoziativ" angibt ist dieser Thread hier der zweite Treffer. Soooo verbreitet scheints dann doch nicht zu sein. Dadurch dass google das Ergebnis aber listet wird es mit der Zeit wahr werden.

volkard

Jester schrieb:

u_ser-l schrieb:

Exponentiation ist vereinbarungsgemäß rechtsassoziativ:
2²n := 2⁽²n)

Dafür findet man bemerkenswert wenige Quellen.

Qelle1:
Bronstein, 2.4.1.1. Regel 6:

Quelle2: http://www.google.de/search?hl=de&q=3^3^3&meta=

Quelle3: http://www10.wolframalpha.com/input/?i=3^3^3

Außerdem: Wäre 3³3=(3³⁾3, dann wäre 3³3=3^(3*3), wie unspannend!

Du hast nur nix gefunden, weil die Exponentation in der falschen Zonentaxonomie liegt. Die Potenzierung ist besser.

volkard schrieb:

Jester schrieb:

u_ser-l schrieb:

Exponentiation ist vereinbarungsgemäß rechtsassoziativ:
2²n := 2⁽²n)

Dafür findet man bemerkenswert wenige Quellen.

Qelle1:
Bronstein, 2.4.1.1. Regel 6:

Quelle2: http://www.google.de/search?hl=de&q=3^3^3&meta=

Quelle3: http://www10.wolframalpha.com/input/?i=3^3^3

Außerdem: Wäre 3³3=(3³⁾3, dann wäre 3³3=3^(3*3), wie unspannend!

Du hast nur nix gefunden, weil die Exponentation in der falschen Zonentaxonomie liegt. Die Potenzierung ist besser.

Ich dachte immer das Wort hätte unser Prof erfunden

Jester

volkard schrieb:

Außerdem: Wäre 3³3=(3³⁾3, dann wäre 3³3=3^(3*3), wie unspannend!

Ja, das hab ich früher auch öfter argumentiert. Das hat man mir hier aber so oft nicht durchgehen lassen, dass ich irgendwann angefangen hab immer genau dazuzusagen was ich meine.

volkard

Es wird auch so lange Zweifel geben, wie der Windows-Taschenrechner es falsch macht.