 O(n) |
Batista
unregistriert
 |
|
Für welche x gilt
![[latex]\sum_{i=1}^{n}x ^i=O(n)[/latex]](http://www.matheboard.de/latex2png/latex2png.php?\sum_{i=1}^{n}x ^i=O(n))
![[latex]s_n=\sum_{i=1}^{n}x^i[/latex]](http://www.matheboard.de/latex2png/latex2png.php?s_n=\sum_{i=1}^{n}x^i)
damit habe ich
![[latex]s_n =\frac{x^{n+1}-1}{x-1}[/latex]](http://www.matheboard.de/latex2png/latex2png.php?s_n =\frac{x^{n+1}-1}{x-1})
für alle x > 1
![[latex]\lim_{n->\infty} \frac{s_n}{n}= \frac{x^{n+1}-1}{n(x-1)}[/latex]](http://www.matheboard.de/latex2png/latex2png.php?\lim_{n->\infty} \frac{s_n}{n}= \frac{x^{n+1}-1}{n(x-1)})
nach hospital regel
![[latex]\lim_{n->\infty} \frac{\lg(n)x^{n}-1}{(x-1)}=\infty[/latex]](http://www.matheboard.de/latex2png/latex2png.php?\lim_{n->\infty} \frac{\lg(n)x^{n}-1}{(x-1)}=\infty)
für x>1 gilt es nicht
|
|
16.05.2015 14:05 |
|
|
|
|
Ich verstehe ehrlich gesagt nicht, was du berechnen willst.
Die Regel von L'Hospital/Bernoulli hast du falsch angewendet, du musst Zähler und Nenner getrennt nach n ableiten.
Gibt ![[latex]\lim_{n \to \infty}\frac{(n+1)\cdot x^n}{x-1}[/latex]](http://www.matheboard.de/latex2png/latex2png.php?\lim_{n \to \infty}\frac{(n+1)\cdot x^n}{x-1})
Und ![[latex]\sum_{i=1}^{n}x^i = \frac{x^{n+1}-x}{x-1}[/latex]](http://www.matheboard.de/latex2png/latex2png.php?\sum_{i=1}^{n}x^i = \frac{x^{n+1}-x}{x-1})
__________________
Syntax Highlighting fürs Board (Link)
|
|
|
16.05.2015 14:30 |
|
|
Batista
unregistriert
|
|
| Zitat: |
Original von eulerscheZahl
Ich verstehe ehrlich gesagt nicht, was du berechnen willst.
|
Ob für die Summe O(n) gilt
| Zitat: |
Original von eulerscheZahl
Die Regel von L'Hospital/Bernoulli hast du falsch angewendet, du musst Zähler und Nenner getrennt nach n ableiten.
Gibt
|
Man muss nach n ableiten, da sich da n verändert und nicht x.
x ist Fest bsp x=2 hat muss man 2^(n+1) ableiten
| Zitat: |
Original von eulerscheZahl
Und |
laut Wikipedia gilt
![[latex]\sum_{i=1}^{n}x^i = \frac{x^{n+1}-1}{x-1}[/latex]](http://www.matheboard.de/latex2png/latex2png.php?\sum_{i=1}^{n}x^i = \frac{x^{n+1}-1}{x-1})
|
|
|
16.05.2015 14:54 |
|
|
|
|
Zur Ableitung: in der Zeile drüber noch richtig geschrieben, um es dann falsch zu machen...
Aber ich bleibe dabei, dass deine Ableitung nicht passt. Sowohl sage als auch wolframalpha kommen auf x^(n + 1)*log(x)
Zur Summenformel: hast du dafür einen Link?
Setzen wir mal x=2 und n=3: 2^1+2^2+2^3 = 2+4+8 = 14
Nach deiner Formel aber (2^4-1)/(2-1) = 15
Mit O(n) meinst du die Laufzeit?
Wenn du nach der Summe geht, wäre es dann O(1), wenn du die Potenz in O(1) berechnen könntest. Ist aber eher O(log(n)) (binäre Exponentiation).
Für die Formel, die du ausgegraben hast, geht das in unter O(n). (ohne Gewähr, die Multiplikation geht ja auch nicht in O(1), keine Lust, das durchzugehen).
__________________
Syntax Highlighting fürs Board (Link)
|
|
|
16.05.2015 15:36 |
|
|
Batista
unregistriert
|
|
Puh übersehen, dass die Summe bei 1 startet....
Wir haben so vereinfacht gesagt. Sei f=O(g), dann existiert der Grenzwert
![[latex]\lim_{n->\infty}\frac{f(n)}{g(n)}<\infty [/latex]](http://www.matheboard.de/latex2png/latex2png.php?\lim_{n->\infty}\frac{f(n)}{g(n)}<\infty )
Das ist auch folgender Ansatz
für alle x > 1
![[latex]\lim_{n->\infty} \frac{s_n}{n}= \frac{x(x^{n+1}-1)}{n(x-1)}[/latex]](http://www.matheboard.de/latex2png/latex2png.php?\lim_{n->\infty} \frac{s_n}{n}= \frac{x(x^{n+1}-1)}{n(x-1)})
nach hospital regel
![[latex]\lim_{n->\infty} \frac{\lg(x) x^{n+1}}{(x-1)}=\infty [/latex]](http://www.matheboard.de/latex2png/latex2png.php?\lim_{n->\infty} \frac{\lg(x) x^{n+1}}{(x-1)}=\infty )
für x>1 gilt es nicht
[quote]Original von eulerscheZahl
Mit O(n) meinst du die Laufzeit?
Für die Formel, die du ausgegraben hast, geht das in unter O(n)/quote]
Ja die Laufzeit
Wie meinst du mit unter O(n)
für x>1 kann es ja nicht von O(n) gelten, so zumindest , nachdem errechneten Grenzwert
|
|
|
16.05.2015 16:18 |
|
|
|
|
Du vergleichst hier Äpfel mit Birnen:
Einmal die Laufzeit in Nenner und dann das Ergebnis im Zähler. Wenn das Ergebnis n wäre, könnte man das in konstanter Laufzeit berechnen, aber nach deiner Berechnung würde man auf lineares Verhalten kommen.
x^n kann man mit log(n) Multiplikationsschritten berechnen.
__________________
Syntax Highlighting fürs Board (Link)
|
|
|
16.05.2015 16:34 |
|
|
Batista
unregistriert
|
|
Ja, stimmt 
|
|
|
16.05.2015 17:53 |
|
|
|
