wie sieht die Oberschrank aus?
ich habe |x|+2log(n-x)+2+C
x=vonanfang bis n mal 1 tretten
Blatt7 Aufgabe1.1
-
- Beiträge: 225
- Registriert: Sa 25. Okt 2008, 12:48
Re: Blatt7 Aufgabe1.1
Hm, das dürfte doch aber schlechter als die allgemeine Abschätzung K(x) <= |x| + c sein.kukugo hat geschrieben:wie sieht die Oberschrank aus?
ich habe |x|+2log(n-x)+2+C
x=vonanfang bis n mal 1 tretten
Mir fällt leider keine gute Abschätzung ein, kann uns vielleicht jemand helfen ?
Danke .
Re: Blatt7 Aufgabe1.1
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.
338364: <Alanna> Saying that Java is nice because it works on all OS's is like saying that anal sex is nice because it works on all genders