0 Daumen
268 Aufrufe

Hallo, 

zerbreche mir schon 2 Tage lang den Kopf über die b. Die a war einfach, einfach 1,2,...,n als Folge angeben

und die Suche wird zu O(n). Aber bei der b habe ich mir folgendes gedacht:


Folge= (1,3,5,7,2,6,4, 8,10,12,14,9,13,11, ...,n)


Was haltet Ihr davon? Ich bin mir schon fast sicher, dass es falsch ist, und nicht allgemein genug ist oder so..

Brauche Eure Hilfe, danke im Voraus!

Bild Mathematik


Viele Grüße und schöne Feiertage


Brezel

Gefragt von

1 Antwort

0 Daumen

Zeichne einen binären Suchbaum mit den Schlüsseln 1, 2, ..., 15, der 4 Ebenen hat. Wenn dieser Baum neu aufgebaut werden müsste, dann könnten die Elemente dazu in der Reihenfolge

8,
4, 12,
2, 6, 10, 14,
1, 3, 5, 7, 9, 11, 13, 15

eingefügt werden.

Verallgemeinere dies auf beliebige n.

Beantwortet von

Genau das ist mein Problem, kriege es nicht verallgemeinert.


Könntest du es bitte veralgemeinern?


Ich weis leider garnicht wie, besten dank!

Für n = 16:

1/2·n,
1/4·n, 3/4·n,
1/8·n, 3/8·n, 5/8·n, 7/8·n,
1/16·n, 3/16·n, 5/16·n, 7/16·n, 9/16·n, 11/16·n, 13/16·n, 15/16·n,
16/16·n

Die 16 rutscht dann zwar in die fünfte Ebene, das ändert aber an dem Θ nichts.

Kann man das irgendwie als summe schreiben? Danke für die schnellsten antworten!

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community
...