O-Notation < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 08:55 Do 26.04.2012 | | Autor: | Naienna |
| Aufgabe | Beweisen sie
, dass
[mm] \summe_{i=1}^{n} i2^i\in [/mm] O-Notation [mm] (n2^n) [/mm] |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Hallo,
ich habe ein Problem in Algorithmen und Datenstrukturen. Die Onotation haben wir gerade neu, ich kann aber damit umgehen, ebenso wie mit Induktionen. Mein Problem ist, dass ich nicht weiß, wie ich anfangen soll. Soll ich erst die Induktion machen? Oder liege ich mit dem Ansatz komplett falsch? Wäre schön wenn mir jemand einen Denkanstoß geben könnte  Danke im Vorfeld für eure Hilfe!
Lg Naienna!
|
|
| |
|
Hallo,
um zu zeigen, dass [mm]\summe_{i=1}^{n} i2^i\in\ O(n2^n)[/mm], musst du eine Konstante [mm]C[/mm], die nicht von [mm]n[/mm] abhängt, finden und ein [mm]N\in\mathbb{N} [/mm] so, dass [mm]\summe_{i=1}^{n} i2^i \leq C2^nn [/mm] für alle [mm]n\geq N[/mm]. Wenn du die Summe in die Form
[mm]\summe_{i=1}^{n} i2^i=2^nn\summe_{i=1}^{n} \frac{2^ii}{2^nn} [/mm] bringst, musst du nur noch [mm]\summe_{i=1}^{n} \frac{2^ii}{2^nn} [/mm] nach oben abschätzen.
Beste Grüße
Spunk
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:15 Mo 30.04.2012 | | Autor: | Naienna |
Das hat geholfen, vielen Dank :)
|
|
|
|
