_Mi amiga/colega que acaba de terminar su licenciatura en Informática se está preparando para un Prueba de aptitud para graduados . Hoy me ha preguntado sobre una cuestión relacionada con Análisis de la complejidad ( Notación Big-O específicamente) que resolví fácilmente, y luego vino otra pregunta en la que me atasqué. El enunciado de la pregunta era:_
¿A qué se aproxima el siguiente algoritmo?
x = m;
y = 1;
while (x - y > e)
{
x = (x + y)/2;
y = m/x;
}
print(x);(Supongamos que m > 1, e > 0).
Opciones:
(A) log m
(B) $m^2$
(C) m^1/2
(D) m^1/3
Inicialmente asumí al ver el código que la respuesta sería (C), ella también llegó a esa respuesta (en realidad no la resolvió), para mi sorpresa era realmente correcta al cotejar la respuesta aquí . Cuando busqué la explicación, decía:
El código dado es una implementación de Método babilónico para la raíz cuadrada
Fácil, ¿verdad? Pero ya que no había nada parecido a la Teoría de Números en nuestro programa de estudios (aunque había Matemáticas de Ingeniería, Matemáticas Discretas y Métodos Numéricos para Ingenieros) No sabía nada de este método, lo que significaba que tenía que resolverlo por mi cuenta (lo que pensé que sería bastante fácil ya que este tipo de preguntas hay que resolverlas en un minuto, si quieres intentar todas las preguntas). Así que cogí un papel y un bolígrafo (por segunda vez) antes de decirle que ya lo resolvería por la mañana y empecé a resolverlo, intentando que fuera sencillo pero al final lo hice complejo (adjunto imágenes).
Lo único que pude deducir es que la complejidad del código era O(logM) y que X se reduce a la mitad (aproximadamente) en cada iteración e Y se duplica (aproximadamente) en cada iteración. Esa no era la respuesta requerida, así que supuse que me faltaba algo, así que busqué el Algoritmo de la Raíz Cuadrada de Babilonia y descubrí que la complejidad era O(logN) y el código proporcionado arriba estaba un poco desordenado ya que
while (x - y > e)que en realidad debía ser
while (x - y)El e sólo se añadió para hacerlo más complejo, también haría que el problema se resolviera por ensayo y error si alguien asumiera e para ser un valor grande (aunque era un trabajo fácil si alguien suponía e=1 y m=100).
Pensé que tal vez si escribo un código para generar algunas estadísticas, entonces podría ser capaz de averiguar algo, así que escribí esto:
#include<iostream>
int main(int argc, char** argv)
{
float x,y=1,m,e;
std::cin>>m>>e;
x=m;
while(x-y>e)
{
x=(x+y)/2;
y=(m/x);
std::cout<<x<<"\t"<<y<<"\t"<<x-y<<std::endl;
}
return 0;
}Al principio, descubrí que e era en realidad un culpable, ya que proporcionar valores más grandes afectaría a la respuesta al no dejarla terminar completamente.
El problema seguía siendo cómo saber que la respuesta sería $m^2$ ? No sé, soy un perdedor en lo que respecta a las matemáticas (y por eso necesito ayuda)
A continuación se muestran algunos datos de muestra de dos entradas, 100000 5 y 100 5
Pude ver que tanto X como Y convergerían a la raíz cuadrada de M, y E era la variable maligna. Ahora, en resumen, suponiendo lo siguiente que:
- El candidato no conoce el método de la raíz cuadrada de Babilonia
- La pregunta tiene que ser intentada idealmente en 1 minuto
- Un candidato bien preparado puede analizar la complejidad fácilmente
- El método de prueba y error es sólo una cuestión de suerte con pocas probabilidades de éxito
- La respuesta no tiene que ser exacta, sino aproximada
¿Cómo se puede resolver este problema?
