Informatiker Board | Berechenbarkeits- und Komplexitätstheorie

Informatiker Board » Themengebiete » Theoretische Informatik » Berechenbarkeits- und Komplexitätstheorie » Funktionen sortieren

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Funktionen sortieren

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

Shizmo
Tripel-As

Dabei seit: 16.10.2015
Beiträge: 174

Funktionen sortieren

Zitatantwort auf diesen Beitrag erstellen

Hallo, wieder mal darf ich Funktionen sortieren a la $[latex]n \in \mathcal{O}(n^2)[/latex]$ , also [latex]n<n^2<2^n<...[/latex]

log ist zur Basis 2 und ln zur Basis e.

Ich hab 16 Stück zur Auswahl großes Grinsen

$[latex]n \ln \log 2^n[/latex]$
$[latex]2^{\log n}[/latex]$
$[latex]n^{1/2}[/latex]$
$[latex]2n \ln n[/latex]$
$[latex]n \ln \ln n[/latex]$
$[latex]\ln n[/latex]$
$[latex]n \ln^2 n[/latex]$
$[latex]n \ln \log n[/latex]$
$[latex]n \ln n^2[/latex]$
$[latex]n^{3/2}[/latex]$
$[latex]2^{n+1}[/latex]$
$[latex]\sqrt{n}+5[/latex]$
$[latex]n\cdot (\sqrt{n}+\ln n)[/latex]$

Okay soweit bin ich schon mal:

(16)
$[latex]\ln n[/latex]$ (7)
$[latex]\sqrt{n} = (n^{1/2} =_{\Theta} \sqrt{n}+5 )[/latex]$ (4,13)
$[latex]n \equiv 2^{\log n}[/latex]$ (2)
$[latex]n \ln \ln n =_{\Theta} n \ln \log n[/latex]$ (6, 9)
$[latex]n \cdot \ln(n) = ( n \ln \log 2^n =_{\Theta} 2n \ln n =_{\Theta} n \ln n^2)[/latex]$ (1,5,10)
$[latex]n \ln^2 n[/latex]$ (8)
$[latex]n^{3/2}[/latex]$ (11)
(3)
$[latex]2^n =_{\Theta} 2^{n+1}[/latex]$ (12,14)

Wenns soweit passt, fehlt nur noch $[latex]n\cdot (\sqrt{n}+\ln n)[/latex]$ . Was mach ich damit?

Wie könnte ich Nr.5 (der sortierten Liste) zeigen, also die Basis ist ja nur eine Konstante, deshalb ist es Theta-äquivalent, aber wie zeige ich das?

Kann man eigentlich sagen, wenn f in KLEIN-o von g ist, es auch automatisch in Groß-O von g ist? Umgekehrt geht natürlich nicht.

LG

22.05.2016 01:34

Nehmen Sie Shizmo in Ihre Freundesliste auf

eulerscheZahl eulerscheZahl ist männlich

Foren Gott

Dabei seit: 04.01.2013
Beiträge: 2.859

$[latex]\ln(\log(n)) = \ln\left(\frac{\ln(n)}{\ln(2)}\right) = \ln(\ln(n)) - \ln(ln(2)) = \ln(\ln(n)) + 0.3665[/latex]$

$[latex]n\cdot (\sqrt{n}+\ln n)[/latex]$
Was ist größer: $[latex]\sqrt n[/latex]$ oder $[latex]\ln n[/latex]$ ?

Zitat:

Kann man eigentlich sagen, wenn f in KLEIN-o von g ist, es auch automatisch in Groß-O von g ist? Umgekehrt geht natürlich nicht.

Ja.
$[latex]f \in \mathcal{O}(g)[/latex]$ heißt ja, dass f nicht größer als g ist (abgesehen von Konstanten).
Klein-o heißt, dass f im Unendlichen echt kleiner als g ist. Also ist es auch nicht größer als g und erfüllt somit die Bedingung von Groß-O.

__________________
Syntax Highlighting fürs Board (Link)

22.05.2016 06:56

Nehmen Sie eulerscheZahl in Ihre Freundesliste auf

Shizmo
Tripel-As

Dabei seit: 16.10.2015
Beiträge: 174

Ah ja okay, das verstehe ich.

$[latex]\sqrt{n}[/latex]$ ist größer als $[latex]\ln n[/latex]$
Also ordne ich es zwischen 6 und 7 ein? Ich tue mir immer etwas schwer mit der Wurzel, aber im Grunde brauch ich mir nur merken, dass sie größer wie log ist und kleiner als linear ist oder?

Kann ich das so begründen, also ich mach jetzt einen Vergleich von
$[latex]n\cdot(\sqrt{n}+\ln n)[/latex]$ und $[latex]n \ln^2 n[/latex]$

Also
$[latex]n\cdot(\sqrt{n}+\ln n) \equiv n \cdot \sqrt{n} + n \cdot \ln(n)[/latex]$ und $[latex]n \ln^2 n \equiv n \cdot \ln(n) \cdot \ln(n)[/latex]$

$[latex]\lim_{n\rightarrow\infty} \frac{n \cdot \sqrt{n} + n \cdot \ln(n)}{n \cdot \ln(n) \cdot \ln(n)} \equiv \lim_{n\rightarrow\infty} \frac{n \cdot \sqrt{n} }{n \cdot \ln(n) \cdot \ln(n)} + \lim_{n\rightarrow\infty} \frac{n \cdot \ln(n) }{n \cdot \ln(n) \cdot \ln(n)} \equiv [/latex]$

Hier brauche ich ja eigtl nur den ersten Summanden betrachten, da dieser ja stärker wächst als der zweite (gibts da eine bessere Begründung?), also:

$[latex]\lim_{n\rightarrow\infty} \frac{n \cdot \sqrt{n} }{n \cdot \ln(n) \cdot \ln(n)} \equiv \lim_{n\rightarrow\infty} \frac{\sqrt{n} }{\ln(n) \cdot \ln(n)}[/latex]$

und das läuft gegen unendlich, kann man das vllt noch irgendwie deutlicher zeigen, evtl abschätzen oder so??

22.05.2016 11:59

eulerscheZahl eulerscheZahl ist männlich

Foren Gott

Dabei seit: 04.01.2013
Beiträge: 2.859

$[latex]n\cdot\sqrt n = n^{3/2}[/latex]$
Und das hast du schon.

__________________
Syntax Highlighting fürs Board (Link)

22.05.2016 18:36

Shizmo
Tripel-As

Dabei seit: 16.10.2015
Beiträge: 174

Hmm ja stimmt. So kann man es auch sehen großes Grinsen

Könnte man trotzdem den Limes-Term noch etwas präzisieren??

22.05.2016 20:22

eulerscheZahl eulerscheZahl ist männlich

Foren Gott

Dabei seit: 04.01.2013
Beiträge: 2.859

Hm, so vielleicht:
$[latex]\lim_{n\rightarrow\infty} \frac{\sqrt{n} }{\ln(n) \cdot \ln(n)} = \lim_{n\rightarrow\infty}\left(\frac{n^{1/4}}{\ln(n)}\right)^2[/latex]$
Das Polynom wächst schneller als der Logarithmus.

__________________
Syntax Highlighting fürs Board (Link)

23.05.2016 09:22

Shizmo
Tripel-As

Dabei seit: 16.10.2015
Beiträge: 174

Ok, vielen Dank!!

23.05.2016 18:30

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » Berechenbarkeits- und Komplexitätstheorie » Funktionen sortieren