TU Wien:Analysis UE (diverse)/Übungen SS19/Beispiel 107

Aus VoWi
Wechseln zu: Navigation, Suche

Bestimmen Sie die Größenordnungen von

  1. (a) 2{,}7n^2-0{,}5n+1
  2. (b) 0{,}35\cdot 2^n+5n^5
  3. (c) \sqrt{1+1{,}1\,n^2}

Hilfreiches[Bearbeiten]

Landau-Symbole[Bearbeiten, WP, 4.62 Definition]

Seien (a_{n})_{n\geq 0} und (b_{n})_{n\geq 0} Folgen. Dann schreibt man für n \to \infty:

  1. (i) a_{n}=O(b_{n}), falls es eine Konstante C>0 gibt, so dass \left | \frac{a_{n}}{b_{n}} \right |\leq C für fast alle n\in \mathbb{N} gilt.
  2. (ii) a_{n}=o(b_{n}), falls \lim_{n\rightarrow \infty }\frac{a_{n}}{b_{n}} = 0 gilt.
  3. (iii) a_{n}\sim b_{n}, falls \lim_{n\rightarrow \infty }\frac{a_{n}}{b_{n}} = 1 gilt.

Lösungsvorschlag von Manül[Bearbeiten]

(a)[Bearbeiten]

2{,}7n^2-0{,}5n+1 = n^2 ( 2{,}7 - \frac{0{,}5}{n} + \frac{1}{n^2} ) \le C \cdot n^2 mit C=2{,}7

\Rightarrow O(n^2)

\frac{2,7}{n} - \frac{0,5}{n^2} + \frac{1}{n^3} \to 0 für n \to \infty

\Rightarrow o(n^3)

\lim_{n \to \infty} \frac{2{,}7n^2-0.5n+1}{2{,}7n^2} = 1 - \frac{0{,}5}{2{,}7n} + \frac{1}{2{,}7n^2} \to 1

\Rightarrow \sim2{,}7n^2

(b)[Bearbeiten]

\frac{0{,}35 \cdot 2^n+5n^5}{2^n} \to 1

\Rightarrow O(2^n)

Anmerkung: 2^n wächst schneller als 5n^5

(c)[Bearbeiten]

\sqrt{1+1{,}1n^2} = n\, \sqrt{\frac{1}{n^2}+1{,}1} \to O(n)

oder \sim\sqrt{1{,}1}n

Manül 13:39, 17. Jun 2008 (CEST)