Asymptotischer Wachstum

[freakC++]

Hallo zusammen,

angenommen ich habe zwei Funktionen f und g, die ich nach ihrem asymptotischen Wachstum sortieren soll.

Sei $f(x) = \pi^{e \cdot 3}$ und $g(x) = 23^9$. Beide liegen ja offensichtlich in O(1). Nun frage ich mich, ob ich erst f oder erst g nennen soll.

Anders ausgedrückt: Wenn ich Funktionen nach dem asymptotischen Wachstum sortieren soll, muss ich dann all diejenigen, die die selbe nächste obere Schranke haben, auch in sich sortieren? Wenn ja, wie? Etwa nach dem Wert, denn hier sind f und g ja Konstanten...

Danke

edit: In welche Komplexitätsklasse würde man eigentlich die Wurzel stecken? Für log(n) reicht es nicht mehr aus. Das nächste wäre dann n*log(n) oder?

[Bashar]

freakC++ schrieb:

Sei $f(x) = \pi^{e \cdot 3}$ und $g(x) = 23^9$. Beide liegen ja offensichtlich in O(1). Nun frage ich mich, ob ich erst f oder erst g nennen soll.

Komische Logik.

f liegt in O(x^5), g liegt in O(x log x), das wirst du wohl nicht bestreiten können.

Anders ausgedrückt: Wenn ich Funktionen nach dem asymptotischen Wachstum sortieren soll, muss ich dann all diejenigen, die die selbe nächste obere Schranke haben, auch in sich sortieren?

Ob du das musst, musst du deinen Professor fragen. Sinnvoll ist es jedenfalls nicht.

[freakC++]

Bashar schrieb:

freakC++ schrieb:

Sei $f(x) = \pi^{e \cdot 3}$ und $g(x) = 23^9$. Beide liegen ja offensichtlich in O(1). Nun frage ich mich, ob ich erst f oder erst g nennen soll.

Komische Logik.

f liegt in O(x^5), g liegt in O(x log x), das wirst du wohl nicht bestreiten können.

Ne, das will ich auch gar nicht bestreiten. Die Logik finde ich nämlich auch etwas komisch und deswegen frage ich ja, ob es eine allgemeine Methode gibt, Funktionen nach ihrem asymptotischen Wachstum zu sorteiren. Wie würdest Du denn f und g sortieren??

[Gast]

freakC++ schrieb:

edit: In welche Komplexitätsklasse würde man eigentlich die Wurzel stecken? Für log(n) reicht es nicht mehr aus. Das nächste wäre dann n*log(n) oder?

Es gibt nicht nur log(n) und nlog(n) und dazwischen nichts mehr. Du kannst die Wurzel in jede Klasse stecken, deren definierende Funktion asymptotisch gleichschnell oder schneller wächst.

freakC++ schrieb:

Wie würdest Du denn f und g sortieren??

Vermutlich ist das für die Aufgabenstellung unerheblich. Beides O(1), fertig.

[volkard]

µ schrieb:

Es gibt nicht nur log(n) und nlog(n) und dazwischen nichts mehr.

Das halte ich für ein Gerücht.

[Gast]

Und ich glaube Du hast nicht richtig gelesen.

[freakC++]

µ schrieb:

Es gibt nicht nur log(n) und nlog(n) und dazwischen nichts mehr. Du kannst die Wurzel in jede Klasse stecken, deren definierende Funktion asymptotisch gleichschnell oder schneller wächst.

Ja, das ist mir eigentlich klar, doch wenn man über die Komplexität von Algorithmen spricht, so gibt man ja meisten immer dieselben oberen Grenzen an. Damit meine ich O(1), O(log n), O(n^k), O(n*log n), O(k^n), O(n!)

Natürlich wäre eine Angabe von $\sqrt{n} \in O(\frac{1}{e^\pi}n^4 - log(n))$ richtig, aber eher sinnfrei, oder?

Danke
LG, freakC++

[Gast]

freakC++ schrieb:

µ schrieb:

Es gibt nicht nur log(n) und nlog(n) und dazwischen nichts mehr. Du kannst die Wurzel in jede Klasse stecken, deren definierende Funktion asymptotisch gleichschnell oder schneller wächst.

Ja, das ist mir eigentlich klar, doch wenn man über die Komplexität von Algorithmen spricht, so gibt man ja meisten immer dieselben oberen Grenzen an. Damit meine ich O(1), O(log n), O(n^k), O(n*log n), O(k^n), O(n!)

Ja es gibt so ein paar übliche Klassen die immer wieder verwendet werden. Beschränkst Du Dich darauf, suchst Du eben die Kleinste, die die Wurzelfunktion noch enthält. (In der Auflistung wäre das Übrigens O(n) (O(n^k) für k=1))

[volkard]

µ schrieb:

Und ich glaube Du hast nicht richtig gelesen.

stimmt.

µ schrieb:

(In der Auflistung wäre das Übrigens O(n) (O(n^k) für k=1))

Sogar k=1/2.

[Michael E.]

freakC++ schrieb:

Ja, das ist mir eigentlich klar, doch wenn man über die Komplexität von Algorithmen spricht, so gibt man ja meisten immer dieselben oberen Grenzen an. Damit meine ich O(1), O(log n), O(n^k), O(n*log n), O(k^n), O(n!)

Schöne heile Erstsemesterwelt. Schau mal hier: http://de.wikipedia.org/wiki/Flüsse_und_Schnitte_in_Netzwerken#Max-Flow_Algorithmen_nach_Ver.C3.B6ffentlichung

Die sind eigentlich noch relativ harmlos. Schau dir z.B. mal Beweise an, dass ein bestimmtes Problem in P liegt.

[Bashar]

freakC++ schrieb:

Bashar schrieb:

f liegt in O(x^5), g liegt in O(x log x), das wirst du wohl nicht bestreiten können.

Ne, das will ich auch gar nicht bestreiten. Die Logik finde ich nämlich auch etwas komisch und deswegen frage ich ja, ob es eine allgemeine Methode gibt, Funktionen nach ihrem asymptotischen Wachstum zu sorteiren. Wie würdest Du denn f und g sortieren??

Zum Sortieren benötigt man eine Ordnungsrelation. Wie wärs damit: $f \leq g :\Longleftrightarrow f \in O(g)$

Was du offenbar willst, ist mathematisch ein bisschen komplizierter. Du willst erstmal die Funktionen in Äquivalenzklassen einteilen, anhand folgender Relation: $f \sim g :\Longleftrightarrow f \leq g \wedge g \leq f$, und dann statt der Funktionen die jeweiligen Repräsentanten (in dem Fall 1) vergleichen. Kann man auch machen, kommt auf dasselbe raus, ist praktisch gesehen sogar einfacher. Entscheidend ist dabei, dass man da wirklich das $\Theta$ und nicht das $O$ benutzt.