Nuestros desarrolladores estrellas han agotado sus depósitos de café, investigando a tiempo completo por la solución, hasta que Iris encontró la contestación en Gitea por lo tanto en este momento la compartimos contigo.
Solución:
Primero, tenga en cuenta que la complejidad asintótica de las operaciones aritméticas establecidas en la literatura común se refiere a operaciones con números con precisión arbitraria, y el tiempo de ejecución se expresa como una función del número deseado de dígitos. Desde el punto de vista de la complejidad asintótica, no tiene sentido pedir operaciones con precisión constante (p. ej., flotantes simples, como mencionó en los comentarios): solo hay $ O (1) $ tales números, por lo tanto, la operación se puede evaluar en tiempo $O(1)$ (por ejemplo, por una tabla de consulta).
Permítanme denotar la precisión deseada como $m$ (ya que usa el $n$ habitual para otra cosa). El resultado que cita es que $sqrt a$ se puede calcular en el tiempo $O(M(m))$, donde $M(m)$ es cualquier función (que satisface algunas condiciones de regularidad suaves) tal que la multiplicación de dos $m Los enteros de $-bit se pueden realizar en el tiempo $M(m)$. (El algoritmo de multiplicación asintóticamente más rápido actualmente conocido tiene $M(m)=mlog m,2^O(log^*m)$.) El algoritmo usa la iteración de Newton $xmapsto x-frac x^2-a2x$. Esta iteración tiene una tasa de convergencia cuadrática, por lo que $O(log m)$ son suficientes iteraciones, y cada paso requiere $O(1)$ multiplicaciones y divisiones, lo que lleva a la estimación $O(M(m)log m) $ en el tiempo total de ejecución. El factor adicional de $log m$ se puede eliminar con la siguiente observación: dado que el número de dígitos correctos se duplica aproximadamente en cada iteración, no tenemos que realizar todas las operaciones con precisión $m$, basta con usar la precisión suficiente para acomodar los dígitos correctos. Por lo tanto, solo la última iteración se realiza con precisión $m$, la penúltima tiene precisión $m/2$, la anterior $m/4$, y así sucesivamente. Entonces el tiempo de ejecución es $O(M(m)+M(m/2)+M(m/4)+cdots)$. Dado que $M$ es esencialmente lineal, puede estar acotado por una serie geométrica, cuya suma es $O(M(m))$. (Tenga en cuenta, por cierto, que el hecho de que la división se pueda hacer en el tiempo $O(M(m))$ también usa un argumento de iteración de Newton similar).
Ahora, ¿qué pasa con las raíces $n$th en general? Puede usar la iteración de Newton nuevamente, como sugiere Denis. El análisis es similar al caso de la raíz cuadrada, pero dado que cada paso toma $O(log n)$ multiplicaciones, se obtiene un límite de $O(M(m)log n)$. Tenga en cuenta que si $n$ se da en binario, $log n$ es la longitud de la entrada, por lo tanto, este es un algoritmo con peor que un tiempo de ejecución cuadrático. Otro enfoque es calcular $sqrt[n]a$ como $exp((log a)/n)$. Usando división binaria, la serie de Taylor para $exp$ y $log$ puede evaluarse en el tiempo $O(M(m)(log m)^2)$; usando algoritmos basados en la media aritmético-geométrica, esto se puede reducir a $O(M(m)log m)$, lo que lleva a un cálculo raíz $n$th con el mismo límite de tiempo. Esto también tiene un factor adicional de $log$, pero es independiente de $n$. No sé cómo calcular $sqrt[n]a$ en el tiempo $O(M(m))$, y soy algo escéptico de que se sepa tal cosa. Bien podría ser que el comentario en el artículo de Alt solo pretenda cubrir el caso de $n$ constante.
El algoritmo de Newton-Raphson usa, para el cálculo de $A^1/p$, la secuencia $u_0=A$, $u_n+1=u_n-frac u_n^pApu_n^p -1$, cuya velocidad de convergencia, siempre cuadrática, es esencialmente independiente de $p$ (y $A$). Entonces, principalmente, pide $ln p$ multiplicaciones y 1 división en cada paso.
Si te apasiona la informática, eres capaz de dejar una reseña acerca de qué te ha gustado de esta sección.