Theorieübung 4 - Skizze der Kritzeleien.

MaxN
Neuling
Neuling
Beiträge: 4
Registriert: 12. Mai 2013 14:36

Theorieübung 4 - Skizze der Kritzeleien.

Beitrag von MaxN »

Hallo,
ich habe folgende Frage zu der Skizze. Laut dieser ist n die Anzahl der Elemente, und log2 n die Höhe. In der Skizze wäre n = 16, die Anzahl der Spalten sollte also log2 (16) = 4 sein, ist in der Skizze aber 5.
Auch dann in unserem speziellen Fall wäre n = |S| = 9, der log2(9) ist aber 3.16.. Was wird bei der Aufgabe erwartet?

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: Theorieübung 4 - Skizze der Kritzeleien.

Beitrag von JannikV »

Hi,

es müssen nicht genau log(n) Zeilen sein. Es geht darum dass es in der Größenordnung von log(n) ist. Ich weiß jetzt nicht ob Komplexitätsbetrachtung schon in der Vorlesung dran war. Dafür ist das wichtig...

Wenn mich nicht alles täuscht müsste die exakte Formel \(\lceil \log_2(n) \rceil + 1\) sein.

Guck bei deinem n=9 mal wie oft du das etwa halbieren musst, bis du jedes Element separiert hast. Da 9 keine Zweierpotenz ist ist der Kasten natürlich nicht mehr ganz rechteckig ^^

VG

MaxN
Neuling
Neuling
Beiträge: 4
Registriert: 12. Mai 2013 14:36

Re: Theorieübung 4 - Skizze der Kritzeleien.

Beitrag von MaxN »

Hallo,

Achso, wenns nur die Größenordnung ist, dann ist es klar - ich hab es als exakten Wert interpretiert :D

Vielen Dank! :D

Benutzeravatar
cofi
Mausschubser
Mausschubser
Beiträge: 86
Registriert: 22. Sep 2009 12:07

Re: Theorieübung 4 - Skizze der Kritzeleien.

Beitrag von cofi »

JannikV hat geschrieben:Wenn mich nicht alles täuscht müsste die exakte Formel \(\lceil \log_2(n) \rceil + 1\) sein
Entweder \(\lceil \log_2(n) \rceil\) oder \(\lfloor \log_2(n) \rfloor + 1\) ;)

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: Theorieübung 4 - Skizze der Kritzeleien.

Beitrag von JannikV »

Da würde bei 9 aber 4 rauskommen. Da brauche ich aber 5.

VG

Benutzeravatar
cofi
Mausschubser
Mausschubser
Beiträge: 86
Registriert: 22. Sep 2009 12:07

Re: Theorieübung 4 - Skizze der Kritzeleien.

Beitrag von cofi »

Die Anzahl der Rekursionsschritte ist allerdings 4 und die ist wichtig.

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: Theorieübung 4 - Skizze der Kritzeleien.

Beitrag von JannikV »

Das stimmt.
Mir ging es jetzt um die Zeilen in der Skizze.
Rekursionstiefe ist in der Tat 4. Und das ist auch wichtig für die Komplexitätsbetrachtung, da hast du recht.

VG

Antworten

Zurück zu „Archiv“