¿Cuál es la complejidad temporal del Algoritmo de Euclides (Límite superior, Límite inferior y Media)?

Question

Lo he buscado en internet en muchos sitios pero ninguno da una borrar respuesta. Todos dan un montón de cosas matemáticas complicadas que no sólo son difíciles de entender para mí, sino que también son irrelevantes, ya que simplemente quiero saber cuál es el límite superior (complejidad en el peor de los casos), el límite inferior y la complejidad del tiempo medio del algoritmo de Euclides. Esto es lo que he recopilado de una miríada de sitios, ninguno dice lo mismo:

Para encontrar $\gcd(a,b)$ con $b<a$ y $b$ con un número de dígitos $h$ :

• Algunos dicen que la complejidad temporal es $O(h^2)$

• Algunos dicen que la complejidad temporal es $O(\log a+\log b)$ (suponiendo que $\log_2$ )

• Otros dicen que la complejidad temporal es $O(\log a\log b)$

• Uno incluso dice esto "Por el teorema de Lame se encuentra un primer número de Fibonacci mayor que b. Si es $F[k+1]$ hay menos de $k$ llamadas recursivas. Por lo tanto, es $O(\log b)$ "

• Todos dicen que el peor caso es cuando $a$ y $b$ son números de Fibonacci consecutivos.

Le agradecería mucho que resolviera todo el asunto de forma concluyente dándome respuestas directas y claras a lo siguiente:

1. ¿Cuál es la complejidad temporal en el peor caso (límite superior) del algoritmo de Euclides?

2. ¿Cuál es la complejidad temporal del caso medio del algoritmo de Euclides?

3. ¿Cuál es el límite inferior del Algoritmo de Euclides (caso mejor) y cuándo se produce?

No tienes idea de cuánto me ayudará tu respuesta. Estoy muy abatido ya que estoy empantanado con lo que se puede considerar un algoritmo bastante simple. Gracias.

Answer 1

Para abordar algunos preliminares, dejemos $T(a,b)$ sea el número de pasos del algoritmo euclidiano, que evalúa repetidamente $\gcd(a,b)=\gcd(b,a\bmod b)$ hasta $b=0$ , suponiendo que $a\geq b$ . Además, deja que $h=\log_{10}b$ sea el número de dígitos de $b$ (más o menos). (Nótese que en estos cálculos, al contar los pasos, ignoramos la cuestión de la complejidad temporal del $\mathrm{mod}$ función. Si asumimos que es $O(1)$ entonces todo lo siguiente también se aplica a la complejidad temporal del algoritmo.

1. En el peor de los casos, como usted ha afirmado, $a=F_{n+1}$ y $b=F_n$ , donde $F_n$ es la secuencia de Fibonacci, ya que calculará $\gcd(F_{n+1},F_n)=\gcd(F_n,F_{n-1})$ hasta llegar a $n=0$ Así que $T(F_{n+1},F_n)=\Theta(n)$ y $T(a,F_n)=O(n)$ . Desde $F_n=\Theta(\varphi^n)$ Esto implica que $T(a,b)=O(\log_\varphi b)$ . Tenga en cuenta que $h\approx log_{10}b$ y $\log_bx={\log x\over\log b}$ implica $\log_bx=O(\log x)$ para cualquier $a$ por lo que el peor caso para el algoritmo de Euclides es $O(\log_\varphi b)=O(h)=O(\log b)$ .

2. El caso medio requiere un poco más de cuidado, ya que depende de las probabilidades de la situación. Para calcularlo con precisión, necesitamos una distribución de probabilidad. Si $a$ es fijo y $b$ se elige uniformemente entre $\mathbb Z\cap[0,a)$ , entonces el número de pasos $T(a)$ es

   $$T(a)=-\frac12+6\frac{\log2}\pi(4\gamma-24\pi^2\zeta'(2)+3\log2-2)+{12\over\pi^2}\log2\log a+O(a^{-1/6+\epsilon}),$$

   o, para ser menos precisos, $T(a)={12\over\pi^2}\log2\log a+O(1)$ . (Fuente: Wikipedia)

3. En el mejor de los casos, $a=b$ o $b=0$ o algún otro caso conveniente como el que ocurre, por lo que el algoritmo termina en un solo paso. Así, $T(a,a)=O(1)$ .

Si estamos trabajando en un ordenador que utiliza cálculos de 32 o 64 bits, como es habitual, entonces el individuo $\bmod$ son de hecho de tiempo constante, por lo que estos límites son correctos. Sin embargo, si estamos haciendo cálculos de precisión arbitraria, para estimar la complejidad temporal real del algoritmo, tenemos que utilizar ese $\bmod$ tiene una complejidad temporal $O(\log a\log b)$ . En este caso, todo el "trabajo" se realiza en el primer paso, y el resto del cómputo es también $O(\log a\log b)$ , por lo que el total es $O(\log a\log b)$ . Sin embargo, quiero destacar que esto sólo se aplica si el número es ese gran que necesitas una precisión arbitraria para calcularlo.

(Esto subraya la diferencia entre la notación big-O del matemático y la notación big-O del programador: en el primer caso, se quiere que el límite sea verdadero $\forall n$ incluso aquellos $n$ que son tan absurdamente grandes que nadie puede escribirlas o almacenarlas en la memoria, mientras que en el segundo caso, los programadores están interesados principalmente en $n\in[0,2^{64}]$ y eso es una estimación liberal. Para ellos, es más importante ver la "contribución principal" a la complejidad del tiempo, y para el algoritmo euclidiano, el número más pequeño impulsa la dificultad del cálculo en general).

Answer 2

El tiempo de ejecución es lineal en la representación numérica mayor: si $a\ge b$ entonces el tiempo de ejecución es $O(\log(a))$