Landau-Symbol (Big-O) < Folgen und Reihen < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:59 Mo 18.02.2019 | | Autor: | magics |
| Aufgabe | Beweisen oder widerlegen Sie die folgenden Aussagen:
a) [mm] $3^n \in 2^{O(n)}$
[/mm]
b) [mm] $(2^n)^3 \in 2^{O(n)}$
[/mm]
c) [mm] $2^{n^3} \in 2^{O(n)}$
[/mm]
d) [mm] $O(2^n) [/mm] = [mm] O(3^n)$
[/mm]
e) [mm] $O(n^2) [/mm] + O(n) = [mm] O(n^2)$
[/mm]
f) $O(n) - O(n) = O(0)$
Verwenden Sie die Tatsache, dass $f(n) [mm] \in O(g(n)),\; gdw.\; c,n_0 \in \IN,\; so\; dass\; \forall\; [/mm] n [mm] \ge n_0 \;gilt\; [/mm] f(n) [mm] \lt [/mm] c*g(n)$ |
Hallo,
ich habe die Aufgaben a) bis f) gelöst, wobei ich mir bei a), b), c) und f) nicht hundertprozentig sicher bin. Hier meine Lösungen:
a) [mm] $3^n \in 2^{O(n)}$
[/mm]
[mm] [quote]$3^n \in 2^{O(n)} \gdw log_2(3^n) [/mm] = O(n) [mm] \gdw n*log_2(3) \le [/mm] c*n [mm] \; [/mm] fuer [mm] \; [/mm] c >> 0$
[mm] \Rightarrow [/mm] Aussage wahr[/quote]
b) [mm] $(2^n)^3 \in 2^{O(n)}$
[/mm]
[mm] [quote]$(2^n)^3 \in 2^{O(n)} \gdw log_2(2^n)^3 [/mm] = O(n) [mm] \gdw n^3 \le [/mm] c*n [mm] \; [/mm] fuer [mm] \; [/mm] c >> 0$
[mm] \Rightarrow [/mm] Aussage wahr[/quote]
c) [mm] $2^{n^3} \in 2^{O(n)}$
[/mm]
[mm] [quote]$2^{n^3} \in 2^{O(n)} \gdw log_2(2^{n^3}) [/mm] = O(n) [mm] \gdw n^3 \le [/mm] c*n$
[mm] \Rightarrow [/mm] Aussage falsch, da [mm] $n^3 \ge [/mm] c*n [mm] \; [/mm] fuer [mm] \; [/mm] c>>0$[/quote]
d) [mm] $O(2^n) [/mm] = [mm] O(3^n)$
[/mm]
[mm] \Rightarrow [/mm] Aussage wahr, da [mm] $2^n \le 3^n$
[/mm]
e) [mm] $O(n^2) [/mm] + O(n) = [mm] O(n^2)$
[/mm]
[mm] [quote]$O(n^2) [/mm] + O(n) = [mm] O(max({n^2, n}) [/mm] = [mm] O(n^2)$
[/mm]
[mm] \Rightarrow [/mm] Aussage wahr[/quote]
f) $O(n) - O(n) = O(0)$
Sinngemäß steht da ja: "Etwas mit Linearer Komplexität minus etwas mit linearer Komplexität ist gleich Komplexität 0. Ich kenne aber nur Komplexität O(1) bei Konstanten, etwas wie O(0) macht gefühlsmäßig keinen Sinn, daher hätte ich gesagt: Aussage falsch."
Es wäre toll, wenn jemand meine Lösungen überfliegt und mich auf mögliche Irrtümer aufmerksam macht.
Beste Grüße
Thomas
|
|
| |
|
> Beweisen oder widerlegen Sie die folgenden Aussagen:
>
> a) [mm]3^n \in 2^{O(n)}[/mm]
> b) [mm](2^n)^3 \in 2^{O(n)}[/mm]
> c) [mm]2^{n^3} \in 2^{O(n)}[/mm]
>
> d) [mm]O(2^n) = O(3^n)[/mm]
> e) [mm]O(n^2) + O(n) = O(n^2)[/mm]
> f) [mm]O(n) - O(n) = O(0)[/mm]
>
> Verwenden Sie die Tatsache, dass [mm]f(n) \in O(g(n)),\; gdw.\; c,n_0 \in \IN,\; so\; dass\; \forall\; n \ge n_0 \;gilt\; f(n) \lt c*g(n)[/mm]
>
> Hallo,
>
> ich habe die Aufgaben a) bis f) gelöst, wobei ich mir bei
> a), b), c) und f) nicht hundertprozentig sicher bin. Hier
> meine Lösungen:
>
> a) [mm]3^n \in 2^{O(n)}[/mm]
> [mm]3^n \in 2^{O(n)} \gdw log_2(3^n) = O(n) \gdw n*log_2(3) \le c*n \; fuer \; c >> 0[/mm]
>
> [mm]\Rightarrow[/mm] Aussage wahr ![[ok]](/images/smileys/ok.gif "[ok]")
>
> b) [mm](2^n)^3 \in 2^{O(n)}[/mm]
> [mm](2^n)^3 \in 2^{O(n)} \gdw log_2(2^n)^3 = O(n) \gdw n^3 \le c*n \; fuer \; c >> 0[/mm]
>
> [mm]\Rightarrow[/mm] Aussage wahr
>
> c) [mm]2^{n^3} \in 2^{O(n)}[/mm]
> [mm]2^{n^3} \in 2^{O(n)} \gdw log_2(2^{n^3}) = O(n) \gdw n^3 \le c*n[/mm]
>
> [mm]\Rightarrow[/mm] Aussage falsch, da [mm]n^3 \ge c*n \; fuer \; c>>0[/mm]
>
> d) [mm]O(2^n) = O(3^n)[/mm]
> [mm]\Rightarrow[/mm] Aussage wahr, da [mm]2^n \le 3^n[/mm] ()
Begründung würde mir nicht reichen, da aus [mm] O(2^n) [/mm] = [mm] O(3^n) [/mm] folgt: [mm] O(3^n) [/mm] = [mm] O(2^n), [/mm] und dann mjüsste auch [mm] 3^n<2^n [/mm] sein.
Nimm lieber wieder den Logarithmus.
>
> e) [mm]O(n^2) + O(n) = O(n^2)[/mm]
> [mm]O(n^2) + O(n) = O(max({n^2, n}) = O(n^2)[/mm]
>
> [mm]\Rightarrow[/mm] Aussage wahr
>
> f) [mm]O(n) - O(n) = O(0)[/mm]
> Sinngemäß steht da ja: "Etwas mit
> Linearer Komplexität minus etwas mit linearer Komplexität
> ist gleich Komplexität 0. Ich kenne aber nur Komplexität
> O(1) bei Konstanten, etwas wie O(0) macht gefühlsmäßig
> keinen Sinn, daher hätte ich gesagt: Aussage falsch."
>
Nimm z.B. [mm] O(x+\wurzel{x}) [/mm] =O(x)
> Es wäre toll, wenn jemand meine Lösungen überfliegt und
> mich auf mögliche Irrtümer aufmerksam macht.
>
> Beste Grüße
> Thomas
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:15 Mo 18.02.2019 | | Autor: | magics |
Besten Dank!
|
|
|
| |
|
Hiho,
also da muss ich doch einiges Ergänzen, da deine Notation doch sehr gruselig ist:
> a) [mm]3^n \in 2^{O(n)}[/mm]
> [mm]3^n \in 2^{O(n)} \gdw log_2(3^n) = O(n) \gdw n*log_2(3) \le c*n \; fuer \; c >> 0[/mm]
>
> [mm]\Rightarrow[/mm] Aussage wahr
Dann kannst du doch bestimmt so ein $c$ angeben, für dass das gilt!
Und ein [mm] $n_0 \in \IN$ [/mm] noch dazu. Denn wähle ich mir $c=1 > 0$ und $n=1 [mm] \in \IN$ [/mm] so steht da [mm] $\log_2(3) \ge [/mm] 1$, was offensichtlich falsch ist.
> b) [mm](2^n)^3 \in 2^{O(n)}[/mm]
> [mm](2^n)^3 \in 2^{O(n)} \gdw log_2(2^n)^3 = O(n) \gdw n^3 \le c*n \; fuer \; c >> 0[/mm]
>
> [mm]\Rightarrow[/mm] Aussage wahr
Hier hast du am Ende stehen: [mm] $n^3 \le [/mm] c*n$ und sagst: Aussage wahr.
aber hier:
> c) [mm]2^{n^3} \in 2^{O(n)}[/mm]
> [mm]2^{n^3} \in 2^{O(n)} \gdw log_2(2^{n^3}) = O(n) \gdw n^3 \le c*n[/mm]
hast du das selbe stehen, und sagst:
> [mm]\Rightarrow[/mm] Aussage falsch, da [mm]n^3 \ge c*n \; fuer \; c>>0[/mm]
Ja was denn nun?
Und auch hier: Wenn wahr, dann c und [mm] n_0 [/mm] angeben, wenn falsch, zeigen, dass für beliebiges c und [mm] n_0 [/mm] ein n existiert, so dass [mm]n^3 > c*n[/mm]
Beachte das strikte größer Zeichen, denn bei Gleichheit wäre noch alles ok.
> d) [mm]O(2^n) = O(3^n)[/mm]
> [mm]\Rightarrow[/mm] Aussage wahr, da [mm]2^n \le 3^n[/mm]
Wie vorher erwähnt: Reicht allein nicht, verwende noch a) dazu.
> e) [mm]O(n^2) + O(n) = O(n^2)[/mm]
> [mm]O(n^2) + O(n) = O(max({n^2, n}) = O(n^2)[/mm]
Das erste Gleichheitszeichen ist zu begründen.
> f) [mm]O(n) - O(n) = O(0)[/mm]
> Sinngemäß steht da ja: "Etwas mit
> Linearer Komplexität minus etwas mit linearer Komplexität
> ist gleich Komplexität 0. Ich kenne aber nur Komplexität
> O(1) bei Konstanten, etwas wie O(0) macht gefühlsmäßig
> keinen Sinn, daher hätte ich gesagt: Aussage falsch."
Gegenfrage: Was ist $O(0)$? Die Menge kannst du direkt angeben.
Verwende doch mal die Definition! Was bedeutet $f [mm] \in [/mm] O(0)$?
Definition anwenden und Bedingung für f ablesen.
Gruß,
Gono
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 09:54 Di 19.02.2019 | | Autor: | magics |
Diese Mitteilung war ein Versehen. Siehe folgende Frage.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 09:57 Di 19.02.2019 | | Autor: | magics |
Hallo, meine Mitteilung sollte eigentlich eine Frage sein, deshalb poste ich sie hier erneut, als Frage:
> Hiho,
>
> also da muss ich doch einiges Ergänzen, da deine Notation
> doch sehr gruselig ist:
Hallo Gono,
vielen Dank für deine vollkommen berechtigte Kritik! Ich sehe ein, was du sagst. Ich korrigiere nun meine Lösungen, wobei ich die Umformungsschritte weglasse. Bei f) bin ich trotzdem nicht so richtig weitergekommen.
a) [mm]3^n \in 2^{O(n)} \gdw n*log_23 = O(n)[/mm]
Somit gilt $n*log_23 [mm] \le [/mm] c * n $ für $c [mm] \ge [/mm] log_23$ und [mm] $n_0=0$
[/mm]
b) [mm](2^n)^3 \in 2^{O(n)} \gdw 3n = O(n)[/mm]
Somit gilt $3n [mm] \le [/mm] c*n$ für $c [mm] \ge [/mm] 3$ und [mm] $n_0 [/mm] = 0$
c) [mm]2^{n^3} \in 2^{O(n)} \gdw n^3 = O(n)[/mm]
[mm] $n^3$ [/mm] wächst aufgrund des polynomiellen Charakters insgesamt stärker als $c*n$, was sich bei bestimmten $c, [mm] n_0$ [/mm] nicht unbedingt sofort bemerkbar macht. Legt man fest [mm] $n_0=c=2 \in \IN$, [/mm] so gilt [mm] $2^3 [/mm] > [mm] 2^2$. [/mm] Damit ist die ursprüngliche Aussage widerlegt.
d) [mm]O(2^n) = O(3^n)[/mm]
Sei [mm] $2^n \in O(3^n)$, [/mm] so gilt [mm] $2^n \le c*3^n$ [/mm] für $c=1$ und [mm] $n_0=1$.
[/mm]
Sei nun [mm] $\red{3^n \in O(2^n)}$, [/mm] so gilt [mm] $\red{3^n \le c*2^n}$ [/mm] für [mm] $\red{c \ge 2}$, [/mm] da [mm] $\red{\limes_{n\rightarrow\infty}\bruch{3^n}{2*(2^n)} = \limes_{}\bruch{3*3*...*3}{4*4*...*4} = 0}$
[/mm]
Wegen [mm] $\red{2^n \in O(3^n)$ und $\red{3^n \in O(2^n)}}$, [/mm] muss die Gleichheit gelten.
Das rote ist natürlich völliger Humbug.
[mm] $3^n \in O(2^n)$ [/mm] kann ja gar nicht korrekt sein. [mm] $\limes_{n\rightarrow\infty}\bruch{3^n}{c*(2^n)}$ [/mm] muss gegen Unendlich gehen, denn sei $c$ eine beliebige große Zahl, darstellbar als Zweierpotenz, also $c = [mm] 2^x$. [/mm] Dann wäre [mm] $\limes_{n\rightarrow\infty}\bruch{3^n}{c*(2^n)} [/mm] = [mm] \limes_{n\rightarrow\infty}\bruch{3^n}{(2^{n+x})}=\bruch{\limes_{n\rightarrow\infty}3^n}{\limes_{n\rightarrow\infty}2^x*2^n)}$. [/mm] Und somit stünde wieder [mm] \limes_{n\rightarrow\infty}\bruch{3^n}{(2^n)} [/mm] zur Debatte, was nur gegen Unendlich gehen kann.
Also ist d) falsch.
e) [mm]O(n^2) + O(n) = O(n^2)[/mm]
Wegen [mm] $n^a \le O(n^b) \; \forall \; [/mm] a [mm] \le [/mm] b$ gilt $O(n) [mm] \subseteq O(n^2)$ [/mm] und somit [mm] $O(n^2) [/mm] + O(n) = [mm] O(max({n^2, n}) [/mm] = [mm] O(n^2)$
[/mm]
f) [mm]O(n) - O(n) = O(0)[/mm]
Nach Definition wäre $O(0)$ zu interpretieren als $f(n) [mm] \le [/mm] c*0$. Wenn ich mir das als Laufzeit eines Algorithmus vorstelle, ist das einfach gar nichts, also eher noch $f(n) = 0$, als $f(n) < 0$. Doch wie genau ich das interpretieren soll, verstehe ich nicht so ganz.
Grüße
Thomas
|
|
|
| |
|
Hiho,
> a) [mm]3^n \in 2^{O(n)} \gdw n*log_23 = O(n)[/mm]
> Somit gilt
> [mm]n*log_23 \le c * n[/mm] für [mm]c \ge log_23[/mm] und [mm]n_0=0[/mm]
> b) [mm](2^n)^3 \in 2^{O(n)} \gdw 3n = O(n)[/mm]
> Somit gilt [mm]3n \le c*n[/mm] für [mm]c \ge 3[/mm] und [mm]n_0 = 0[/mm]
> c) [mm]2^{n^3} \in 2^{O(n)} \gdw n^3 = O(n)[/mm]
> [mm]n^3[/mm] wächst
> aufgrund des polynomiellen Charakters insgesamt stärker
> als [mm]c*n[/mm],
Das ist korrekt (und man hätte hier fast aufhören können).
> was sich bei bestimmten [mm]c, n_0[/mm] nicht unbedingt sofort bemerkbar macht.
Das ist Palaver und keine Begründung.
> Legt man fest [mm]n_0=c=2 \in \IN[/mm], so
> gilt [mm]2^3 > 2^2[/mm]. Damit ist die ursprüngliche Aussage widerlegt.
Leider nicht. Du hast es nur für ein c widerlegt. Du musst aber zeigen, dass es kein einziges $c > 0$ gibt, so dass [mm] $n^3 \le [/mm] cn$ ab einem bestimmten [mm] $n_0$.
[/mm]
Aber auch das ist kein Problem:
Sei [mm] $n_0 [/mm] > [mm] \sqrt{c}$ [/mm] dann gilt für alle $n [mm] \ge n_0$ [/mm] und beliebiges $c > 0$:
[mm] $n^3 [/mm] = [mm] n^2\cdot [/mm] n [mm] \ge n_0^2\cdot [/mm] n > [mm] \sqrt{c}^2\cdot [/mm] n = cn$, d.h.
[mm] $n^3 [/mm] > nc$
Damit ist das Gewünschte gezeigt.
> d) [mm]O(2^n) = O(3^n)[/mm]
> Sei [mm]2^n \in O(3^n)[/mm], so gilt [mm]2^n \le c*3^n[/mm]
> für [mm]c=1[/mm] und [mm]n_0=1[/mm].
> Sei nun [mm]\red{3^n \in O(2^n)}[/mm], so gilt [mm]\red{3^n \le c*2^n}[/mm]
> für [mm]\red{c \ge 2}[/mm], da
> [mm]\red{\limes_{n\rightarrow\infty}\bruch{3^n}{2*(2^n)} = \limes_{}\bruch{3*3*...*3}{4*4*...*4} = 0}[/mm]
>
> Wegen [mm]\red{2^n \in O(3^n)[/mm] und [mm]\red{3^n \in O(2^n)}}[/mm], muss
> die Gleichheit gelten.
> Das rote ist natürlich völliger Humbug.
> [mm]3^n \in O(2^n)[/mm] kann ja gar nicht korrekt sein.
> [mm]\limes_{n\rightarrow\infty}\bruch{3^n}{c*(2^n)}[/mm] muss gegen
> Unendlich gehen, denn sei [mm]c[/mm] eine beliebige große Zahl,
> darstellbar als Zweierpotenz, also [mm]c = 2^x[/mm]. Dann wäre
> [mm]\limes_{n\rightarrow\infty}\bruch{3^n}{c*(2^n)} = \limes_{n\rightarrow\infty}\bruch{3^n}{(2^{n+x})}=\bruch{\limes_{n\rightarrow\infty}3^n}{\limes_{n\rightarrow\infty}2^x*2^n)}[/mm].
> Und somit stünde wieder
> [mm]\limes_{n\rightarrow\infty}\bruch{3^n}{(2^n)}[/mm] zur Debatte,
> was nur gegen Unendlich gehen kann.
> Also ist d) falsch.
Kurz gesagt: Ja.
Deine Begründung kann man aber kürzen.
Damit die Aussage stimmt, müsste ja [mm] $3^n \in O(2^n)$ [/mm] gelten.
Wie du bereits erkannt hast, müsste dann aber gelten, dass
[mm] $\lim_{n\to\infty} \frac{3^n}{2^n} \le [/mm] c$
Es gilt aber [mm] $\lim_{n\to\infty} \frac{3^n}{2^n} [/mm] = [mm] $\lim_{n\to\infty} \left(\frac{3}{2}\right)^n [/mm] = [mm] +\infty$
[/mm]
Insbesondere gilt damit für alle $c > 0$, dass [mm] $\lim_{n\to\infty} \frac{3^n}{2^n} [/mm] > c$
So hättest du übrigens auch die Aufgabe davor begründen können, nur dass man dort halt stattdessen [mm] $\lim_{n\to\infty} n^2$ [/mm] betrachtet hätte.
> e) [mm]O(n^2) + O(n) = O(n^2)[/mm]
> Wegen [mm]n^a \le O(n^b) \; \forall \; a \le b[/mm]
> gilt [mm]O(n) \subseteq O(n^2)[/mm] und somit [mm]O(n^2) + O(n) = O(max({n^2, n}) = O(n^2)[/mm]
Ok.
> f) [mm]O(n) - O(n) = O(0)[/mm]
> Nach Definition wäre [mm]O(0)[/mm] zu
> interpretieren als [mm]f(n) \le c*0[/mm].
Erstmal: Ich nehme an, dass ihr nur nichtnegative Funktionen betrachtet?
Denn ganz allgemein bedeutet $f [mm] \in [/mm] O(g)$ nämlich $|f| [mm] \le [/mm] c|g|$
Dann: Du hast nun also $0 [mm] \le [/mm] f(n) [mm] \le c\cdot [/mm] 0 = 0$ für alle $n [mm] \ge n_0$
[/mm]
Was bedeutet das nun also für $f$?
Es bleibt f also nichts anderes übrig, als irgendwann Null zu werden.
> Wenn ich mir das als
> Laufzeit eines Algorithmus vorstelle, ist das einfach gar
> nichts, also eher noch [mm]f(n) = 0[/mm], als [mm]f(n) < 0[/mm]. Doch wie
> genau ich das interpretieren soll, verstehe ich nicht so
> ganz.
Wenn man noch annimmt, dass ein Algorithmus monoton wachsend in [mm] $n\in\IN$ [/mm] ist, bedeutet die Bedingung $f [mm] \in [/mm] O(0)$ also nichts anderes, dass $f$ die Nullfunktion sein muss!
D.h. im Allgemeinen gilt:
$f [mm] \in [/mm] O(0)$ bedeutet, dass $f$ irgendwann konstant Null wird ab einem [mm] $n_0 \in \IN$.
[/mm]
Ist f zusätzlich monoton wachsend, wie bei einem Algorithmus, so ist $f$ von Anfang an konstant Null und damit die Nullfunktion.
Gebe also eine Funktion an, die in $O(n) - O(n)$ ist, aber nie Null wird und schon hast du [mm]O(n) - O(n) \not= O(0)[/mm] gezeigt.
Gruß,
Gono
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 09:10 Do 21.02.2019 | | Autor: | magics |
Deine Hilfe war absolut der Hammer, vielen Dank!
Beste Grüße
Thomas
|
|
|
|
