O - Notationen Beweisführung

17.10.2014, 10:50

0664jester

O - Notationen Beweisführung

Hallo,

ich habe hier ein paar übungen zu asymptotischen Schranken:

Das erste ist, glaube ich richtig! Dient nur zur demonstration!
1) $\begin{eqnarray*} 2^{n+1} = O(2^{n}) \end{eqnarray*}$
z.z.: $\begin{eqnarray*} \exists c > 0, n_{0} \in \mathbb N \end{eqnarray*}$

$\begin{eqnarray*} 2^{n+1} \leq 2^{n}c /:2^{n} \end{eqnarray*}$
$\begin{eqnarray*} 2 \leq c \end{eqnarray*}$

Antwort: Ab 2 kann c gewählt werden und erfüllt die Bedingung $\begin{eqnarray*} \exists c > 0 \end{eqnarray*}$

Jetzt kommt das eigentliche Beispiel:
2) $\begin{eqnarray*} O(8^{n}) = 3^{O(n)} \end{eqnarray*}$

Naja, ich habe hier zweimal Onotationen und hatte den Fall noch nicht.
Gibt's da was zum Nachlesen? Ich habe noch nichts gefunden.

Gruß,
jester

17.10.2014, 13:27

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von 0664jester
2) $\begin{eqnarray*} O(8^{n}) = 3^{O(n)} \end{eqnarray*}$

Die Gleichheit würde ich hier so lesen, dass du behauptest

$\begin{align*} f\in O\left( 8^n \right) \;\Longleftrightarrow\; f\in 3^{O(n)} \end{align*}$ .

Das stimmt aber nicht: Nur $\begin{align*} \Rightarrow \end{align*}$ ist richtig; für $\begin{align*} \Leftarrow \end{align*}$ genügt bereits das Gegenbeispiel $\begin{align*} f(n)=3^{2n}=9^n \end{align*}$ .

17.10.2014, 19:40

0664jester

Auf diesen Beitrag antworten »

Wie kommst du da auf das Gegenbeispiel?

Gruß

17.10.2014, 20:08

HAL 9000

Auf diesen Beitrag antworten »

Dieses "Wie kommst du"-Gefrage ist irrelevant - wichtig ist, dass es ein Gegenbeispiel ist

21.10.2014, 10:27

0664jester

Auf diesen Beitrag antworten »

Hallo,

was heißt überhaupt das 3^O(n)? also ich meine das O(n)?

21.10.2014, 10:56

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von 0664jester
was heißt überhaupt das 3^O(n)?

Das müsstest eigentlich du beantworten, denn du hast das ja so aufgeschrieben! M.E. ist diese Schreibweise nicht gerade sauber.

Jedenfalls habe ich $\begin{align*} f\in 3^{O(n)} \end{align*}$ so aufgefasst, dass es eine Funktion $\begin{align*} g\in O(n) \end{align*}$ gibt, so dass $\begin{align*} \left| \frac{f(n)}{3^{g(n)}} \right| \end{align*}$ beschränkt ist. Wenn du $\begin{align*} f\in 3^{O(n)} \end{align*}$ anders meinst, dann teile dies bitte mit!

21.10.2014, 11:30

0664jester

Auf diesen Beitrag antworten »

nein, passt so. Danke Freude

23.10.2014, 13:38

0664jester

Auf diesen Beitrag antworten »

Ich habe gerade das bsp nochmals überdacht und frage mich, ob das so reicht.

Denn wir haben jetzt nur ein Gegenbeispiel gezeigt, aber es könnte ja auch beispiele geben, wo es funktioniert. Hmm, vllt muss es ja nicht für alle stimmen...

28.10.2014, 18:55

0664jester

Auf diesen Beitrag antworten »

Hallo

Zitat:

Original von HAL 9000

$\begin{align*} f\in O\left( 8^n \right) \;\Longleftrightarrow\; f\in 3^{O(n)} \end{align*}$ .

Das stimmt aber nicht: Nur $\begin{align*} \Rightarrow \end{align*}$ ist richtig; für $\begin{align*} \Leftarrow \end{align*}$ genügt bereits das Gegenbeispiel $\begin{align*} f(n)=3^{2n}=9^n \end{align*}$ .

Warum ist das " $\begin{align*} \Rightarrow \end{align*}$ ist richtig;" richtig, ich versteh dass nicht.
Kannst da ein bisschen mehr erklären.

Ich hab's so:
$\begin{align*} 8 < 3^b \Rightarrow b > \frac{log(8)}{log(3)} \Rightarrow q =a *lim (\frac{8}{3^b}^n ) = 0 \end{align*}$

Gruß,
Jester

Neue Frage »

Antworten »

O - Notationen Beweisführung

Verwandte Themen