bäume und höhe < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:37 Do 21.06.2007 | | Autor: | AriR |
hey leute
verstehe leider nicht so genau wie man die höhe eines vollständigen baumes in O(log(n)) einordnet, wobei n die anzahl der knoten ist.
ich würde es schon verstehen, wenn n die anzahl der blätter des baumes wäre.
dann wäre ja [mm] n=2^h [/mm] wobei h die höhe wäre
und das wäre ja wiederum [mm] h=log_2(n)O(log(n))
[/mm]
aber n ist ja hier die anzahl aller knoten.
kann das vielleicht mal jemand bitte klar stellen, wenn er kurz zeit hat?
gruß :)
|
|
| |
|
Hallo,
Du meinst sicher vollständige Binärbäume.
Ich gehe dieses Thema ganz naiv an - ich wohne im Wald:
Höhe h Anz. d. Blätter Gesamtzahl d. K. bei Höhe h
0 1 1
1 2---------------------------------------------1+2
2 [mm] 2^2-----------------------------1+2+2^2
[/mm]
[mm] \vdots
[/mm]
h [mm] 2^h------------------------1+2+2^2+...+2^h=\summe_{i=0}^{h}2^i=\bruch{1-2^{h+1}}{1-2}
[/mm]
Bestimmt kannst Du hieraus Dein O(log(n)) machen.
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:37 Do 21.06.2007 | | Autor: | AriR |
sowas in der art habe ich mir auch gedacht, nur wenn ich weiter machen würde, würde ich auf folgendes kommen:
[mm] h*2^h> \summe_{i=0}^h 2^h [/mm] = [mm] \bruch{1-2^{h+1}}{1-2}
[/mm]
und dann bekomme ich da wiederum raus:
[mm] 2^h [/mm] > [mm] \bruch1h [/mm] * [mm] \bruch{1-2^{h+1}}{1-2} [/mm]
und somit [mm] h>\log_2 \bruch{1-2^{h+1}}{1h-2h} [/mm]
aber damit komme ich auch nicht weiter :'(
kannst du mir vielleicht noch etwas weiterhelfen +g+
gruß :)
|
|
|
| |
|
>
> kannst du mir vielleicht noch etwas weiterhelfen +g+
Leider nicht, weil ich vom Thema nicht die geringste Ahnung habe und mich außerdem vor "klein o" und "groß O" prinzipiell fürchte.
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:16 Do 21.06.2007 | | Autor: | felixf |
Hallo!
> sowas in der art habe ich mir auch gedacht, nur wenn ich
> weiter machen würde, würde ich auf folgendes kommen:
>
> [mm]h*2^h> \summe_{i=0}^h 2^h[/mm] = [mm]\bruch{1-2^{h+1}}{1-2}[/mm]
>
> und dann bekomme ich da wiederum raus:
>
> [mm]2^h[/mm] > [mm]\bruch1h[/mm] * [mm]\bruch{1-2^{h+1}}{1-2}[/mm]
>
> und somit [mm]h>\log_2 \bruch{1-2^{h+1}}{1h-2h}[/mm]
>
> aber damit komme ich auch nicht weiter :'(
Wieso so kompliziert?
Es ist ja $n = [mm] \sum_{i=0}^h 2^i [/mm] = [mm] \frac{1 - 2^{h+1}}{1 - 2} [/mm] = [mm] 2^{h+1} [/mm] - 1$, und damit $h = [mm] \log_2(n [/mm] + 1) - 1$. Und [mm] $\log_2(n [/mm] + 1) - 1$ ist jetzt in [mm] $O(\log [/mm] n)$, denn es ist ja [mm] $\log_2(n [/mm] + 1) - 1 [mm] \le \log_2(2 [/mm] n) - 1 = [mm] \log_2(n) [/mm] + [mm] \log_2(2) [/mm] - 1 = [mm] \log_2(n)$.
[/mm]
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:30 Do 21.06.2007 | | Autor: | AriR |
das angela sich vor etwas fürchtet hätte ich ja nie gedacht :D
aber wir sind auch alle nur menschen +g+
ich glaube jetzt habe ich es acuh.
danke an euch beide ;)
|
|
|
|
