[martiniano]

Hola.

Aquí ando con otro problema de complejidades computacionales. Me dan el siguiente código y me piden textualmente: "Explica la complejidad":

Código: [Seleccionar]

programa F(n)
k,m: vector
  escribir (k,1)
  escribir (m,1)
  mayor_o_igual(m,n)
  mientras leer(acepta)=0 hacer
    sucesor(k)
    mult(m,k)
    mayor_o_igual(m,n)
  fmientras
fin

El programa mayor_o_igual(m,n) deja el acepta en \( 1 \) si \( m\geq{n} \) y en \( 0 \) en otro caso.
El programa sucesor(k) calcula el número siguiente a \( k \).
El programa mult(m,k) calcula el producto \( m\cdot{k} \) y lo escribe en \( m \) utilizando el algoritmo elemental de multiplicación de números naturales.

Lo que hace este programa es calcular el menor natural \( p \) tal que \( p! \) es mayor que otro natural \( n \) dado. En lo sucesivo \( \left |{x}\right | \) significa "el número de dígitos de la representación binaria de \( x \)". Yo he pensado lo siguiente:

El tiempo de las sentencias anteriores al bucle no depende de \( \left |{n}\right | \), es decir, es constante.

El bucle se ejecuta \( p \) veces, en la \( k-\textrm{ésima} \) de las cuales calcula:

1) El sucesor de \( k \), se hace en un tiempo \( O(\left |{k}\right | \)
2) El producto \( m\cdot{k} \), que se puede hacer en \( O(\left |{m}\right |\cdot{\left |{k}\right |})=O(\left |{(k-1)!}\right |\cdot{\left |{k}\right |}) \)
3) El valor lógico de mayor_o_igual(m,n), que se hace en \( O(min(\left |{m}\right |,\left |{n}\right |))\subseteq{O(\left |{n}\right |)} \)

En total, el número de operaciones que deben hacerse es del orden de:

\( O(\left |{1}\right |+|2|+...+|p|+|1|\cdot{}|0!|+|2|\cdot{}|1!|+...+|p|\cdot{}|(p-1)!|+\underbrace{|n|+...+|n|}_{p\textrm{ veces}})=O(|1|\cdot{}|0!|+|2|\cdot{}|1!|+...+|p|\cdot{}|(p-1)!|+p\cdot{\left |{n}\right |}) \)

Y básicamente, hasta aquí he llegado. He intentado cosas pero no me ha salido nada demasiado interesante, como por ejemplo, utilizar los teoremas de Stolz y de Stirling para calcular la parte principal de \( |1|\cdot{}|0!|+|2|\cdot{}|1!|+...+|p|\cdot{}|(p-1)!|\sim{}\log(1)\log(0!)+\log(2)\log(1!)+...+\log(p)\log((p-1)!) \), pero no lo he acabado de sacar. Tampoco creo que vayan por ahí los tiros, ya que no veo cómo se puede dejar después todo en función sólo de \( \left |{n}\right | \).

¿Alguien me podría proporcionar algunas recomendaciones o directrices para resolver problemas de este estilo? No acabo de pillarles el "tranquillo".

Agradezco de antemano cualquier tipo de comentario y de ayuda. Un saludo.

[geómetracat]

A mí estas cosas también me han costado siempre bastante, si bien tampoco he trabajado mucho estas cosas. Lo ideal sería que contestara alguien que supiera más sobre esto y tuviera más práctica con cálculos de complejidad, pero mientras eso pasa te dejo unos comentarios.

A mí lo que haces me parece correcto. Ahora puedes obtener una cota superior en la complejidad haciendo lo siguiente (si no me he equivocado):
\( O(\sum_{k=1}^{p} |k||(k-1)!|) = O(\sum_{k=1}^{p} \log(k) \log((k-1)!)) \leq O(\sum_{k=1}^{p} \log(k)\log(p!)) = O(\log(p!)^2) = O(|n|^2) \).
En el último paso uso que \( p! \leq n < (p+1)! \) de donde \( \log (p!) \leq \log n < \log(p+1)! \), y usando por ejemplo que \( O(\log(p!)) = O(p\log p) \) (fórmula de Stirling), se sigue que \( O(\log p!) = O(\log (p+1)!) \) y por tanto \( O(|n|) = O(\log n) = O(\log (p!)) \).

Por otro lado el último término da \( O(p|n|) = O(p \log (p!)) = O(p^2 \log p) \leq O(p^2 (\log p)^2) = O(|n|^2) \), así que este término no es importante.

No sé si la cota es óptima. He hech algunos experimentos con Python y parece que sí que crece cuadráticamente en la longitud del input, pero tampoco estoy 100% seguro.

[martiniano]

Hola.

A mí lo que haces me parece correcto. Ahora puedes obtener una cota superior en la complejidad haciendo lo siguiente (si no me he equivocado):
\( O(\sum_{k=1}^{p} |k||(k-1)!|) = O(\sum_{k=1}^{p} \log(k) \log((k-1)!)) \leq O(\sum_{k=1}^{p} \log(k)\log(p!)) = O(\log(p!)^2) = O(|n|^2) \).
En el último paso uso que \( p! \leq n < (p+1)! \) de donde \( \log (p!) \leq \log n < \log(p+1)! \), y usando por ejemplo que \( O(\log(p!)) = O(p\log p) \) (fórmula de Stirling), se sigue que \( O(\log p!) = O(\log (p+1)!) \) y por tanto \( O(|n|) = O(\log n) = O(\log (p!)) \).

Por otro lado el último término da \( O(p|n|) = O(p \log (p!)) = O(p^2 \log p) \leq O(p^2 (\log p)^2) = O(|n|^2) \), así que este término no es importante.

No sé si la cota es óptima. He hecho algunos experimentos con Python y parece que sí que crece cuadráticamente en la longitud del input, pero tampoco estoy 100% seguro.

Ya veo... Buscas una cota superior para la complejidad. Yo lo intenté también, pero no fui capaz de encontrarla. Muchas gracias, me resulta muy útil. Tal vez la cota no sea óptima, pero, sinceramente, pienso que es muy posible que fuese esta la respuesta que se esperaba y que el enunciado esté un poco mal redactado. Intentaré buscar a ver una cota inferior cuya complejidad sea también \( O(|n|^2) \) y así ya estaría. Si no, intentaré hacerle llegar esto al profe a través de un amigo que sí que está matriculado en la asignatura para ver si esperaba algo más. Si logro avanzar o hay cualquier novedad te digo cosas.

Una vez más, gracias por todo. Un saludo.

[geómetracat]

Sí, si se te ocurre algo o consigues la solución oficial, ponla por aquí por favor. Este problema me ha dejado un poco "picado". 

[martiniano]

Hola.

Le he comunicado esto al profe y ha dicho que el ejercici, aun estando entre los recomendados a los alumnos, se sale de los contenidos del curso. Así que de momento no hemos avanzado mucho más...

Saludos.

PD. Yo estoy más que satisfecho de haber llegado a donde hemos llegado. Así que gracias.