Saltar al contenido

Complejidad temporal del algoritmo de Euclides

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 > b pero a < b
  • B pequeña: 2b > a pero b < 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) < a y 2a <= bentonces b se reduce al menos a la mitad, por lo que a+b disminuido en al menos 25%
  • Pequeña B: a % b < b y 2b <= aentonces a se reduce al menos a la mitad, por lo que a+b disminuido en al menos 25%
  • Pequeña A: b se convertirá b-aque es menor que b/2decreciente a+b por lo menos 25%.
  • B pequeña: a se convertirá a-bque es menor que a/2decreciente a+b por lo menos 25%.
  • Igual: a+b cae a 0que obviamente está disminuyendo a+b por lo menos 25%.

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).

ingrese la descripción de la imagen aquí

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).

ingrese la descripción de la imagen aquí

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:

ingrese la descripción de la imagen aquí

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.

¡Haz clic para puntuar esta entrada!
(Votos: 0 Promedio: 0)



Utiliza Nuestro Buscador

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *