Mantén la atención ya que en esta división vas a encontrar la respuesta que buscas.Este post fue analizado por nuestros expertos para garantizar la calidad y exactitud de nuestro contenido.
Solución:
Un truco para analizar la complejidad temporal del algoritmo de Euclides es seguir lo que sucede en dos iteraciones:
a', b' := a % b, b % (a % b)
Ahora a y b disminuirán, en lugar de solo uno, lo que facilita el análisis. Puedes dividirlo en casos:
- Pequeña A:
2a <= b - Pequeña B:
2b <= a - Pequeña A:
2a > bperoa < b - B pequeña:
2b > aperob < a - Igual:
a == b
Ahora mostraremos que cada caso individual disminuye el total a+b por al menos una cuarta parte:
- Pequeña A:
b % (a % b) < ay2a <= bentoncesbse reduce al menos a la mitad, por lo quea+bdisminuido en al menos25% - Pequeña B:
a % b < by2b <= aentoncesase reduce al menos a la mitad, por lo quea+bdisminuido en al menos25% - Pequeña A:
bse convertiráb-aque es menor queb/2decrecientea+bpor lo menos25%. - B pequeña:
ase convertiráa-bque es menor quea/2decrecientea+bpor lo menos25%. - Igual:
a+bcae a0que obviamente está disminuyendoa+bpor lo menos25%.
Por lo tanto, por análisis de caso, cada paso doble disminuye a+b por lo menos 25%. Hay un número máximo de veces que esto puede suceder antes a+b se ve obligado a caer por debajo 1. El número total de pasos (S) hasta que lleguemos a 0 debe satisfacer (4/3)^S <= A+B. Ahora solo trabájalo:
(4/3)^S <= A+B
S <= lg[4/3](A+B)
S is O(lg[4/3](A+B))
S is O(lg(A+B))
S is O(lg(A*B)) //because A*B asymptotically greater than A+B
S is O(lg(A)+lg(B))
//Input size N is lg(A) + lg(B)
S is O(N)
Entonces, el número de iteraciones es lineal en el número de dígitos de entrada. Para los números que caben en los registros de la CPU, es razonable modelar las iteraciones tomando un tiempo constante y pretender que el total El tiempo de ejecución del gcd es lineal.
Por supuesto, si está tratando con números enteros grandes, debe tener en cuenta el hecho de que las operaciones de módulo dentro de cada iteración no tienen un costo constante. En términos generales, el tiempo de ejecución asintótico total será n^2 veces un factor polilogarítmico. Algo como n^2 lg(n) 2^O(log* n). El factor polilogarítmico se puede evitar utilizando en su lugar un gcd binario.
La forma adecuada de analizar un algoritmo es determinando sus peores escenarios. El peor caso de Euclidean GCD ocurre cuando están involucrados los pares de Fibonacci.
void EGCD(fib[i], fib[i - 1])donde i > 0.
Por ejemplo, optemos por el caso en el que el dividendo es 55 y el divisor es 34 (recuerde que todavía estamos tratando con números de Fibonacci).
Como puede notar, esta operación costó 8 iteraciones (o llamadas recursivas).
Probemos números de Fibonacci más grandes, a saber, 121393 y 75025. También podemos notar aquí que tomó 24 iteraciones (o llamadas recursivas).
También puede notar que cada iteración produce un número de Fibonacci. Por eso tenemos tantas operaciones. De hecho, no podemos obtener resultados similares solo con números de Fibonacci.
Por lo tanto, la complejidad del tiempo estará representada por un pequeño Oh (límite superior), esta vez. El límite inferior es intuitivamente Omega(1): caso de 500 dividido por 2, por ejemplo.
Resolvamos la relación de recurrencia:
Entonces podemos decir que Euclidean GCD puede hacer la operación log(xy) a lo sumo.
Hay una gran mirada a esto en el artículo de wikipedia.
Incluso tiene un buen gráfico de complejidad para pares de valores.
No lo es O(a%b).
Se sabe (ver artículo) que nunca dará más pasos que cinco veces el número de dígitos del número menor. Entonces, el número máximo de pasos crece a medida que el número de dígitos (ln b). El costo de cada paso también crece con el número de dígitos, por lo que la complejidad está limitada por O(ln^2 b) donde b es el número más pequeño. Ese es un límite superior, y el tiempo real suele ser menor.
Aquí puedes ver las comentarios y valoraciones de los usuarios
Agradecemos que quieras añadir valor a nuestra información asistiendo con tu veteranía en las críticas.