Esta pregunta es sólo por diversión. Espero que se reciba con el mismo espíritu bobalicón con el que la escribí.
Acabo de tener el placer de leer la obra de Knuth "La complejidad de las canciones" y pensé que sería divertidísimo que alguien hiciera un análisis de la complejidad de una versión infinita de "La canción del bebé tiburón" o dos, similar a la realizada en ibid. en "O' McDonald tenía una granja" .
Aquí está la letra:
"Bebé tiburón, doo doo doo doo doo.
Bebé tiburón, doo doo doo doo doo.
Bebé tiburón, doo doo doo doo doo.
¡Tiburón bebé!
"Mamá tiburón, doo doo doo doo doo.
Mamá tiburón, doo doo doo doo doo.
Mamá tiburón, doo doo doo doo doo.
¡Mamá tiburón!
"Papá tiburón, doo doo doo doo doo.
Papá tiburón, doo doo doo doo doo doo.
Papá tiburón, doo doo doo doo doo doo.
¡Papá tiburón!
"Abuela tiburón, doo doo doo doo doo doo.
Abuela tiburón, doo doo doo doo doo doo.
Abuela tiburón, doo doo doo doo doo doo.
¡Abuela tiburón!
"Abuelo tiburón, doo doo doo doo doo.
Abuelo tiburón, doo doo doo doo doo.
Abuelo tiburón, doo doo doo doo doo.
¡Abuelo tiburón!
"Vamos a cazar, doo doo doo doo doo doo.
Vamos a cazar, doo doo doo doo doo doo.
Vamos a cazar, doo doo doo doo doo doo.
¡Vamos a cazar!
"Huye, doo doo doo doo doo.
Huye, doo doo doo doo doo.
Huye, doo doo doo doo doo.
¡Huye!
"A salvo por fin, doo doo doo doo doo.
Por fin a salvo, doo doo doo doo doo.
Por fin a salvo, doo doo doo doo doo.
¡Por fin a salvo!
"Es el fin, doo doo doo doo doo.
Es el fin, doo doo doo doo doo.
Es el fin, doo doo doo doo doo.
Es el fin".
Esquema posible:
Sea $D=\text{"doo"}^6$ .
Sea $R(x)=x\, D,\, x\, D,\, x\, D,\, x$ .
Sea $$\begin{align} S_b&=\text{"baby shark"},\\ S_m&=\text{"mommy shark"},\\ S_d&=\text{"daddy shark"},\\ S_{gm}&=\text{"grandma shark"},\\ S_{gp}&=\text{"grandpa shark"},\\ H&=\text{"let's go hunt"}, \\ R_a&=\text{"run away"}, \\ S&=\text{"safe at last"}, \\ E&=\text{"it's the end"}. \end{align}$$
Sea $U(a, b, c, d, e, f, g, h, i)=R(a)R(b)R(c)R(d)R(e)R(f)R(g)R(h)R(i)$ .
Una canción de orden $n$ se definiría del siguiente modo:
$$\begin{align} \mathscr{S}_0&=\epsilon, \\ \mathscr{S}_n&=U(S_b,S_m, S_d, S_{gm}, S_{gp}, H, R_a, S,E)\mathscr{S}_{n-1} \end{align}$$
para $n\ge 1$ .
Y así sucesivamente
El problema:
No estoy seguro de cómo seguir a partir de ahí.
Pensamientos:
Debería ser sencillo. De hecho, creo que la complejidad de la canción, tal como se define, es sólo $O(1)$ .
Yo tampoco estoy contento con el esquema actual. El $R(E)$ deberían ir al "final" en lugar de intercaladas a lo largo de todo el texto, por un lado.
Alternativamente
¿Qué pasaría con la complejidad de la canción si insistiéramos en que, en su lugar, pasáramos de $R(\text{"baby shark"})$ a $R(\text{"grandpa shark"})$ como al principio, pero luego, con $$V_\ell(S_{gm}, S_{gp})=R(G_\ell S_{gm})R(G_\ell S_{gp}),$$ donde $G_\ell=\text{great}^\ell$ para $\ell\ge 1$ seguimos con el $V_\ell$ s?
De nuevo, sospecho que es $O(1)$ pero lo creo mucho menos que en el primer caso.
Por favor, ayuda :)
