Komplexitätstheorie: Wie vorgehen bei diesem Beispiel?

17.11.2018, 18:07	MatheNoob32	Auf diesen Beitrag antworten »
Komplexitätstheorie: Wie vorgehen bei diesem Beispiel? Ich setze mich gerade mit der folgenden Aussage auseinander: $\begin{eqnarray} <br /> 10^{\sqrt(n)} \in O(2^n)<br /> \end{eqnarray}$ Die Frage ist jetzt, ob diese stimmt oder nicht, und warum. Lösungsideen Mein größtes Ziel wäre es, den Term links so umzuformen, dass man auf ein Vielfaches von $\begin{eqnarray} 2^n \end{eqnarray}$ kommt. Leider ist die Wurzel hier sehr unhandlich; leider ist ja $\begin{eqnarray} 10^{(n^{\frac{1}{2}})} \neq (10^n)^{\frac{1}{2}} \end{eqnarray}$ , weshalb ich das $\begin{eqnarray} n \end{eqnarray}$ nicht in die erste Potenz kriege. Alternativ habe ich auch versucht, ein bisschen abzuschätzen, was denn nun größer sein könnte. Ich habe jetzt einfach mal abgeschätzt, dass die Wurzelfunktion $\begin{eqnarray} 10^{\sqrt{n}} \approx \frac{1}{4} \cdot n + 0,8 \end{eqnarray}$ . Man könnte also sagen, nach 4 Schritten verzehnfacht sich der Funktionswert links. Währenddessen versechzehnfacht er sich rechts, was die Aussage gültig machen dürfte. Aber ob das ein ausreichender Beweis ist?
23.11.2018, 08:03	HAL 9000	Auf diesen Beitrag antworten »
Nachzuweisen ist die Beschränktheit von $\begin{eqnarray} \frac{10^{\sqrt{n}}}{2^n} \end{eqnarray}$ für $\begin{eqnarray} n\to\infty \end{eqnarray}$ . Das sieht man sofort durch Logarithmieren, z.B. mit dem dekadischen Logarithmus: $\begin{eqnarray} \lg\left( \frac{10^{\sqrt{n}}}{2^n} \right) = \lg\left( 10^{\sqrt{n}}\right) - \lg\left(2^n\right) = \sqrt{n} - n\lg(2) = \sqrt{n}\left(1 - \sqrt{n}\lg(2)\right) \to -\infty \end{eqnarray}$ für $\begin{eqnarray} n\to\infty \end{eqnarray}$ , daraus folgt $\begin{eqnarray} \lim_{n\to\infty} \frac{10^{\sqrt{n}}}{2^n} = 0 \end{eqnarray}$ , also sogar $\begin{eqnarray} 10^{\sqrt{n}}\in o\left(2^n\right) \end{eqnarray}$ .

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »