Seite 1 von 1
Blatt7 Aufgabe1.1
Verfasst: Mo 14. Dez 2009, 19:01
von kukugo
wie sieht die Oberschrank aus?
ich habe |x|+2log(n-x)+2+C
x=vonanfang bis n mal 1 tretten
Re: Blatt7 Aufgabe1.1
Verfasst: Di 15. Dez 2009, 21:47
von Christian S.
kukugo hat geschrieben: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
.
Re: Blatt7 Aufgabe1.1
Verfasst: Mi 16. Dez 2009, 10:05
von 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.