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

Para abordar algunos preliminares, dejemos$T(a,b)$Sea el número de pasos tomados en el algoritmo euclidiano, que evalúa repetidamente$\gcd(a,b)=\gcd(b,a\bmod b)$hasta$b=0$, asumiendo$a\geq b$. También, deja$h=\log_{10}b$Sea el número de dígitos en$b$(Da o toma). (Tenga en cuenta que en estos cálculos, al contar los pasos, ignoramos la cuestión de la complejidad temporal de la$\mathrm{mod}$función. Si suponemos 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 dicho,$a=F_{n+1}$y$b=F_n$, dónde$F_n$es la sucesión de Fibonacci, ya que calculará$\gcd(F_{n+1},F_n)=\gcd(F_n,F_{n-1})$hasta que llega a$n=0$, entonces$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 de los casos para el algoritmo de Euclides es$O(\log_\varphi b)=O(h)=O(\log b)$.

2. El caso promedio 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 de$\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 menor precisión,$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 sucede algún otro caso conveniente como ese, por lo que el algoritmo termina en un solo paso. De este modo,$T(a,a)=O(1)$.

Si estamos trabajando en una computadora con cálculos de 32 bits o de 64 bits, como es común, entonces el individuo$\bmod$las operaciones 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, entonces para estimar la complejidad de tiempo real del algoritmo, necesitamos usar eso$\bmod$tiene complejidad de tiempo$O(\log a\log b)$. En este caso, todo el "trabajo" se realiza en el primer paso, y el resto del cálculo también se realiza$O(\log a\log b)$, entonces el total es$O(\log a\log b)$. Sin embargo, quiero enfatizar que esto solo se aplica si el número es tan grande que necesita precisión arbitraria para calcularlo.

(Esto subraya la diferencia entre la notación O grande del matemático y la O grande del programador: en el primer caso, desea que el límite sea verdadero$\forall n$, incluso esos$n$que son tan absurdamente grandes que nadie puede escribirlos o almacenarlos en la memoria, mientras que en el segundo caso, los programadores están interesados ​​principalmente en$n\in[0,2^{64}]$, y esa es una estimación generosa. 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).

el tiempo de ejecución es lineal en la representación de números más grandes: si$a\ge b$entonces el tiempo de ejecución es$O(\log(a))$