Höhe eines Heaps < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:45 Sa 28.04.2012 | | Autor: | bandchef |
| Aufgabe | Zeigen Sie die Aussage:
Ein Heap mit n-Elementen hat die Höhe [mm] $\lfloor [/mm] log(n) [mm] \rfloor$ [/mm] |
Ich weiß, wenn ich einen Heap zeichne, dann entspricht die Höhe de2 Heaps in der Tat [mm] $\lfloor [/mm] log(n) [mm] \rfloor$.
[/mm]
Ich hab hier ein Bild von einem Heap: http://s7.directupload.net/file/d/2874/qh39mqm9_jpg.htm
Wie man sehen kann hat dieser Heap 7 Elemente, also n=7. Wenn ich nun die Höhe des Heaps berechnen will, gilt: [mm] $h=\lfloor log_2(n) \rfloor [/mm] = [mm] \lfloor log_2(7) \rfloor [/mm] = 2$
Wie aber zeigt man nun diese Aussage?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:59 Sa 28.04.2012 | | Autor: | felixf |
Moin!
> Zeigen Sie die Aussage:
>
> Ein Heap mit n-Elementen hat die Höhe [mm]\lfloor log(n) \rfloor[/mm]
>
> Ich weiß, wenn ich einen Heap zeichne, dann entspricht die
> Höhe de2 Heaps in der Tat [mm]\lfloor log(n) \rfloor[/mm].
>
> Ich hab hier ein Bild von einem Heap:
> http://s7.directupload.net/file/d/2874/qh39mqm9_jpg.htm
>
> Wie man sehen kann hat dieser Heap 7 Elemente, also n=7.
> Wenn ich nun die Höhe des Heaps berechnen will, gilt:
> [mm]h=\lfloor log_2(n) \rfloor = \lfloor log_2(7) \rfloor = 2[/mm]
Ein Heap mit $k$ vollen Zeilen hat [mm] $2^k [/mm] - 1$ Elemente. Damit es genau $k$ Zeilen sind, muss also [mm] $2^{k-1} [/mm] - 1 < n [mm] \le 2^k [/mm] - 1$ sein.
Jetzt musst du zeigen, dass hieraus $k = [mm] \lfloor \log_2 [/mm] n [mm] \rfloor$ [/mm] folgt.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:11 Sa 28.04.2012 | | Autor: | bandchef |
Anzahl Elemente bei k vollen Zeilen:
n = [mm] 2^k-1 [/mm] (wenn ich mein Bespiel einsetze, dann stimmt das auch)
[mm] $2^{k-1}-1 [/mm] < n [mm] \leq 2^k-1$
[/mm]
[mm] $\Leftrightarrow 2^{k-1}
[mm] $\Leftrightarrow \frac{2^{k-1}}{2^k}< [/mm] n [mm] \leq [/mm] 1$
[mm] $\Leftrightarrow \frac{1}{2}< [/mm] n [mm] \leq [/mm] 1$
[mm] $\Leftrightarrow log_2(\frac{1}{2}) [/mm] < [mm] log_2(n) \leq log_2(1)$
[/mm]
[mm] $\Leftrightarrow [/mm] -1 < [mm] log_2(n) \leq [/mm] 0$
Irgendwie stimmt das aber nicht so ganz, oder?
PS: Der selbst gezeichnete Heap ist NICHT Teil der Aufgabe! Den hab ich mir nur gezeichnet, um einen Heap besser vor Augen zu haben! Ich soll [mm] $\lfloor lgo_2(n) \rfloor$ [/mm] nicht konkret für einen vollen Heap zeigen, sondern allgemein!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:22 Sa 28.04.2012 | | Autor: | felixf |
Moin!
> Anzahl Elemente bei k vollen Zeilen:
>
> n = [mm]2^k-1[/mm] (wenn ich mein Bespiel einsetze, dann stimmt das
> auch)
Wieso setzt du dieses $n$ ein? Das ist doch falsch.
> [mm]2^{k-1}-1 < n \leq 2^k-1[/mm]
> [mm]\Leftrightarrow 2^{k-1}
Nein? Aus $1 < 2 [mm] \le [/mm] 2$ folgt doch nicht $0 < 2 [mm] \le [/mm] 1$.
> [mm]\Leftrightarrow \frac{2^{k-1}}{2^k}< n \leq 1[/mm]
Und das noch weniger. Aus $1 < 2 [mm] \le [/mm] 3$ folgt nicht [mm] $\frac{1}{3} [/mm] < 2 [mm] \le [/mm] 1$.
> Irgendwie stimmt das aber nicht so ganz, oder?
Genau.
> PS: Der selbst gezeichnete Heap ist NICHT Teil der Aufgabe!
Das ist schon klar. Du sollst auch nicht $n = [mm] 2^k [/mm] - 1$ setzen.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:29 Sa 28.04.2012 | | Autor: | bandchef |
$ [mm] 2^{k-1}-1 [/mm] < n [mm] \leq 2^k-1 [/mm] $
[mm] $\Leftrightarrow 2^{k-1} [/mm] < n+1 [mm] \leq 2^k$
[/mm]
[mm] $\Leftrightarrow \frac{2^{k-1}}{2^k} [/mm] < [mm] \frac{n+1}{2^k} \leq [/mm] 1$
[mm] $\Leftrightarrow \frac{2^{k-1}}{2^k} [/mm] < [mm] \frac{n+1}{2^k} \leq [/mm] 1$
[mm] $\Leftrightarrow \frac{1}{2} [/mm] < [mm] \frac{n+1}{2^k} \leq [/mm] 1$
[mm] $\Leftrightarrow \frac{1}{2} [/mm] < [mm] \frac{n+1}{2^k} \leq [/mm] 1$
[mm] $\Leftrightarrow [/mm] -1 < [mm] log_2(n+1)-k \leq [/mm] 0$
Ist das jetzt besser?
Edit: Ich muss quasi k isolieren, oder? Irgendwie kapier ich grad nicht wie ich dass mit so einer zweiseitige Ungleichung gehen soll...
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 13:02 So 29.04.2012 | | Autor: | felixf |
Moin!
> [mm]2^{k-1}-1 < n \leq 2^k-1[/mm]
> [mm]\Leftrightarrow 2^{k-1} < n+1 \leq 2^k[/mm]
>
> [mm]\Leftrightarrow \frac{2^{k-1}}{2^k} < \frac{n+1}{2^k} \leq 1[/mm]
>
> [mm]\Leftrightarrow \frac{2^{k-1}}{2^k} < \frac{n+1}{2^k} \leq 1[/mm]
>
> [mm]\Leftrightarrow \frac{1}{2} < \frac{n+1}{2^k} \leq 1[/mm]
>
> [mm]\Leftrightarrow \frac{1}{2} < \frac{n+1}{2^k} \leq 1[/mm]
>
> [mm]\Leftrightarrow -1 < log_2(n+1)-k \leq 0[/mm]
>
> Ist das jetzt besser?
Ja, wenn auch etwas redundant.
Du haettest auch wesentlich einfacher zum Ziel kommen koennen, wenn du direkt nach der ersten Aequivalenz den Logarithmus genommen haettest. Dann staend da $k - 1 < [mm] \log_2(n [/mm] + 1) [mm] \le [/mm] k$.
> Edit: Ich muss quasi k isolieren, oder? Irgendwie kapier
> ich grad nicht wie ich dass mit so einer zweiseitige
> Ungleichung gehen soll...
Fangen wir nochmal von vorne an. Du hast [mm] $2^{k-1} [/mm] - 1 < n [mm] \le 2^k [/mm] - 1$, wobei alles ganze Zahlen sind. Damit ist dies aequvialent zu [mm] $2^{k-1} \le [/mm] n [mm] \le 2^k [/mm] - 1$.
Aus der linken Ungleichung [mm] ($2^{k-1} \le [/mm] n$) bekommst du mit Hilfe des Logarithmus sofort $k - 1 [mm] \le \log_2(n)$; [/mm] da $k - 1$ eine ganze Zahl ist, gilt dann auch $k - 1 [mm] \le \lfloor \log_2(n) \rfloor$.
[/mm]
Die rechte Ungleichung ($n [mm] \le 2^k [/mm] - 1$) liefert $n < [mm] 2^k$, [/mm] und Logarithmus liefert [mm] $\lfloor \log_2(n) \rfloor \le \log_2(n) [/mm] < k$.
Also gilt $k - 1 [mm] \le \lfloor \log_2(n) \rfloor [/mm] < k$, und da alles ganze Zahlen sind, muss [mm] $\lfloor \log_2(n) \rfloor [/mm] = k - 1$ sein. So. Wie kommst du damit jetzt weiter?
LG Felix
|
|
|
| |
|
Ich kann soweit alles nachvollziehen bis auf, Zitat: "Also gilt $ k - 1 [mm] \le \lfloor \log_2(n) \rfloor [/mm] < k $, und da alles ganze Zahlen sind, muss $ [mm] \lfloor \log_2(n) \rfloor [/mm] = k - 1 $ sein."
Ich verstehe nicht, wie du von dieser Ungleichung auf eine "normale" Gleichung mit einem "Istgleich" kommst...
Was mir aber wiederum einleuchtet ist: $ [mm] \lfloor \log_2(n) \rfloor [/mm] = [mm] \underbrace{k - 1}_{=h} [/mm] $. Die Höhe $h$ eines Heaps ist ja die Zeilenanzahl - 1, also gilt: $h = k-1$.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:20 Di 01.05.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
