Hice el siguiente programa de Haskell (sin golf) para el desafío del código de golf de calcular los primeros valores de A229037 .
Esta es mi propuesta de solución para calcular el º valor:
a n | n<1 = 0
| n<3 = 1
| otherwise = head (goods n)
goods n = [x | x <- [1..], isGood x n]
isGood x n = and [ x - a(n-k) /= a(n-k) - a(n-k-k) || a(n-k-k) == 0 | k <- [1..n] ]
Tenga en cuenta que Haskell no almacena en caché ni memoriza automáticamente estos valores.
La página OEIS para la secuencia da el hecho de que , por lo que podría ser reemplazado por , ya que el algoritmo nunca alcanzará una mayor que .[1..]
[1..(n+1)/2]
Intentando contar las llamadas a funciones, deduje el siguiente límite superior , el número de llamadas a funciones que el algoritmo toma para una entrada :
Conecté la fórmula final en Mathematica:
RSolve[{T[n] == 2*T[n - 1]*n*(n + 1), T[1] == 1}, T[n], n]
Y obtuve, después de una pequeña simplificación:
La proporción promedio entre esto y el tiempo de ejecución del programa Haskell, para es y la desviación estándar de las proporciones es de alrededor de . (Curiosamente, el diagrama de registro de las proporciones parece ser una línea recta).
Las relaciones con la primera línea, que define , tienen una desviación media y estándar de y , respectivamente, pero su trama salta mucho.
¿Cómo puedo conocer mejor la complejidad temporal de este algoritmo?
Aquí está el algoritmo en C válido (menos las declaraciones directas), que creo que es más o menos equivalente al código Haskell:
int a(int n){
if (n < 1) {
return 0;
} else if (n < 3) {
return 1;
} else {
return lowestValid(n);
}
}
int lowestValid(int n){
int possible = 1; // Without checking, we know that this will not exceed (n+1)/2
while (notGood(possible, n)) {
possible++;
}
return possible;
}
int notGood(int possible, int n){
int k = 1;
while (k <= n) {
if ( ((possible - a(n-k)) == (a(n-k) - a(n-2*k))) && (a(n-2*k) != 0) ) {
return 1;
} else {
k++;
}
}
return 0;
}
La versión C tarda unos 5 minutos en calcular y la versión Haskell tarda aproximadamente lo mismo en .
Los primeros tiempos de las versiones:
Haskell: [0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,1.0e-2,3.0e-2,9.0e-2,0.34,1.42,11.77,71.68,184.37,1815.91]
C: [2.0e-6, 1.0e-6, 1.0e-6, 2.0e-6, 1.0e-6, 6.0e-6, 0.00003,0.00027, 0.002209, 0.005127, 0.016665, 0.080549, 0.243611, 0.821537, 4.56265, 24.2044, 272.212]
fuente
a
Respuestas:
Puede escribir su recurrencia como En particular, . Esto significa que la secuencia crece muy rápidamente, y en particular Por lo tanto, Esto significa que Y entonces Esto mejora en su límite por una raíz cuadrada.
fuente