Blatt7 Aufgabe1.1

[kukugo]

wie sieht die Oberschrank aus?
ich habe |x|+2log(n-x)+2+C
x=vonanfang bis n mal 1 tretten

[Christian S.]

wie sieht die Oberschrank aus?
ich habe |x|+2log(n-x)+2+C
x=vonanfang bis n mal 1 tretten

Hm, das dürfte doch aber schlechter als die allgemeine Abschätzung K(x) <= |x| + c sein.
Mir fällt leider keine gute Abschätzung ein, kann uns vielleicht jemand helfen ?
Danke .

[Johann]

Ich find da auch nichts. Ich suche schon die ganze Zeit irgendwie ein tolle Kodierung, deren worst case besser als |w| ist. Ich hab da jetzt dann an Huffman oder so gedacht, aber das ist bei worst case schlechter, also lässt sich gar nicht als Schranke heranziehen. Die Tatsache, dass die 1 nur k mal vorkommt, bedeutet ja, dass man theoretisch Blöcke kodieren kann (also Run Length Encoding), was aber im worst case auch viel schlechter als |w| ist. Keine Ahnung.