0 Daumen
1,5k 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

Avatar 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.

Avatar von 5,7 k

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

Ähnliche Fragen

0 Daumen
1 Antwort
+1 Daumen
1 Antwort
Gefragt 14 Jun 2016 von Gast
0 Daumen
1 Antwort
Gefragt 15 Dez 2020 von anonym123123

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community