Asymptot. Laufzeitverhalten < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Betrachte B-Bäume von Grad t, t beliebig, aber fest. Uns interessiertdas asymptotische Laufzeitverhalten der Einfüge-Operation ( mit Beweis!).
a) Die Einfügeoperation verwende binäre Suche innerhalb eines Knotens. Wie ist die asymp. worst-case Laufzeit des Einfügens in einen B-Baum mit n Schlüsseln?
b) Eine andere Implementierung der Einfügeoperation verwende lineare Suche. Wie ist nun das asymp. worst-case Verhalten? |
Hallo zusammen,
ich weiß nicht genau, wie ich die Aufgabe lösen soll bzw. das alles beweisen soll.
Ich hoffe, es kann mir jemand einen Tipp geben, wie man das macht.
Dafür wäre ich sehr dankbar.
Ich hab mir zur a) folgendes überlegt:
Die Höhe h eines B-Baumes ist doch beschränkt durch [mm] log_{t} \bruch{n+1}{2}. [/mm] Die Anzahl der Knoten ist mind. [mm] 2t^{h} [/mm] -1 und binäre Suche ist O(log n).
Kann ich das sagen, dass die Laufzeit des Einfügens im worst-case [mm] O(log_{t} [/mm] n) [mm] 2t^{h} [/mm] -1, also [mm] O(log_{t} [/mm] n) mal Anzahl der Knoten im Baum?
Oder reicht auch [mm] O(log_{t} [/mm] n) * h?
Ich weiß nicht, wie ich das zeigen soll und ob das was ich gemacht habe so stimmt.
Bei der b) hab ich statt [mm] O(log_{t} [/mm] n) O(n) genommen, weil die lineare Suche von dieser Größenordnung ist und dies dann auch mal [mm] 2t^{h} [/mm] -1 genommen.
Wie gesagt, dass sind nur meine Lösungsansätze, die auch total falsch sein können.
Ich hoffe, es kann mir jemand weiter helfen.
VG, wetterfrosch
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:20 Di 30.05.2006 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
