¿Puede un programa calcular la complejidad de un algoritmo?

Question

¿Hay alguna manera de calcular la complejidad temporal de un algoritmo programáticamente? Por ejemplo, ¿cómo podría calcular la complejidad de una función fibonacci(n)?

Answer 1

La indecidibilidad del halting problem dice que ni siquiera se puede decir si un algoritmo termina. Estoy bastante seguro de que de esto se desprende que generalmente no se puede resolver la complejidad de un algoritmo.

Answer 2

Cuente las operaciones aritméticas, los accesos de memoria y el espacio de memoria utilizado dentro de fibbonacci() o lo que sea, mida su tiempo de ejecución. Haga esto con diferentes entradas, vea las tendencias emergentes, el comportamiento asintótico.

Answer 3

No en general. Si el algoritmo consiste en bucles simples anidados for, p.

for (int i=a; i<b; ++i) 

entonces usted sabe que esto contribuirá (b-a) pasos. Ahora, si b o a o ambos dependen de n, entonces puede obtener una complejidad de eso. Sin embargo, si usted tiene algo más exótico, como

for (int i=a; i<b; i=whackyFunction(i)) 

entonces usted realmente necesita entender lo que hace whackyFunction(i).

De manera similar, las declaraciones break pueden arruinar esto, y las declaraciones while pueden ser una causa perdida ya que es posible que ni siquiera sea capaz de saber si el ciclo finalizó.

Answer 4

Las medidas generales como cyclomatic complexity son útiles para darle una idea de las partes más complejas de su código, pero es un mecanismo relativamente simple.

Answer 5

Si bien es imposible de hacer en todos los casos (a menos que ejecute su propio analizador de código y solo observe los bucles y los impactos en sus valores), todavía es posible hacer una prueba de recuadro negro con un límite superior tiempo establecido. Es decir, tiene alguna variable que se establece para determinar que una vez que la ejecución de un programa pasa esta vez se considera que se ejecuta para siempre.

A partir de esto, su código sería similar a este (código rápido y sucio lo siento, es un poco detallado y la matemática podría estar desactivada para potencias más grandes que no he comprobado).

Puede mejorarse mediante el uso de un conjunto de valores de entrada en lugar de generar aleatoriamente algunos, y también al verificar un rango más amplio de valores, debe poder verificar cualquier entrada en comparación con otras dos entradas y determinar todas las patrones de duración del método

Estoy seguro de que hay formas mucho mejores (es decir, más precisas) de calcular O entre un conjunto de números dados que el que se muestra aquí (que no relaciona demasiado el tiempo de ejecución entre los elementos).

static void Main(string[] args) 
{ 
    var sw = new Stopwatch(); 

    var inputTimes = new Dictionary<int, double>(); 

    List<int> inputValues = new List<int>(); 
    for (int i = 0; i < 25; i++) 
    { 
     inputValues.Add(i); 
    } 

    var ThreadTimeout = 10000; 
    for (int i = 0; i < inputValues.Count; i++) 
    { 
     int input = inputValues[i]; 
     var WorkerThread = new Thread(t => CallMagicMethod(input)) { Name = "WorkerThread" }; 
     sw.Reset(); 
     Console.WriteLine("Input value '{0}' running...", input); 
     sw.Start(); 
     WorkerThread.Start(); 
     WorkerThread.Join(ThreadTimeout); 
     sw.Stop(); 
     if (WorkerThread.IsAlive) 
     { 
      Console.WriteLine("Input value '{0}' exceeds timeout", input); 
      WorkerThread.Abort(); 
      //break; 
      inputTimes.Add(input, double.MaxValue); 
      continue; 
     } 
     inputTimes.Add(input, sw.Elapsed.TotalMilliseconds); 
     Console.WriteLine("Input value '{0}' took {1}ms", input, sw.Elapsed.TotalMilliseconds); 

    } 

    List<int> indexes = inputTimes.Keys.OrderBy(k => k).ToList(); 

    // calculate the difference between the values: 
    for (int i = 0; i < indexes.Count - 2; i++) 
    { 
     int index0 = indexes[i]; 
     int index1 = indexes[i + 1]; 
     if (!inputTimes.ContainsKey(index1)) 
     { 
      continue; 
     } 
     int index2 = indexes[i + 2]; 
     if (!inputTimes.ContainsKey(index2)) 
     { 
      continue; 
     } 

     double[] runTimes = new double[] { inputTimes[index0], inputTimes[index1], inputTimes[index2] }; 

     if (IsRoughlyEqual(runTimes[2], runTimes[1], runTimes[0])) 
     { 
      Console.WriteLine("Execution time for input = {0} to {1} is roughly O(1)", index0, index2); 
     } 
     else if (IsRoughlyEqual(runTimes[2]/Math.Log(index2, 2), runTimes[1]/Math.Log(index1, 2), runTimes[0]/Math.Log(index0, 2))) 
     { 
      Console.WriteLine("Execution time for input = {0} to {1} is roughly O(log N)", index0, index2); 
     } 
     else if (IsRoughlyEqual(runTimes[2]/index2, runTimes[1]/index1, runTimes[0]/index0)) 
     { 
      Console.WriteLine("Execution time for input = {0} to {1} is roughly O(N)", index0, index2); 
     } 
     else if (IsRoughlyEqual(runTimes[2]/(Math.Log(index2, 2) * index2), runTimes[1]/(Math.Log(index1, 2) * index1), runTimes[0]/(Math.Log(index0, 2) * index0))) 
     { 
      Console.WriteLine("Execution time for input = {0} to {1} is roughly O(N log N)", index0, index2); 
     } 
     else 
     { 
      for (int pow = 2; pow <= 10; pow++) 
      { 
       if (IsRoughlyEqual(runTimes[2]/Math.Pow(index2, pow), runTimes[1]/Math.Pow(index1, pow), runTimes[0]/Math.Pow(index0, pow))) 
       { 
        Console.WriteLine("Execution time for input = {0} to {1} is roughly O(N^{2})", index0, index2, pow); 
        break; 
       } 
       else if (pow == 10) 
       { 
        Console.WriteLine("Execution time for input = {0} to {1} is greater than O(N^10)", index0, index2); 
       } 
      } 
     } 
    } 

    Console.WriteLine("Fin."); 
} 

private static double variance = 0.02; 

public static bool IsRoughlyEqual(double value, double lower, double upper) 
{ 
    //returns if the lower, value and upper are within a variance of the next value; 
    return IsBetween(lower, value * (1 - variance), value * (1 + variance)) && 
     IsBetween(value, upper * (1 - variance), upper * (1 + variance)); 
} 

public static bool IsBetween(double value, double lower, double upper) 
{ 
    //returns if the value is between the other 2 values +/- variance 
    lower = lower * (1 - variance); 
    upper = upper * (1 + variance); 

    return value > lower && value < upper; 
} 

public static void CallMagicMethod(int input) 
{ 
    try 
    { 
     MagicBox.MagicMethod(input); 
    } 
    catch (ThreadAbortException tae) 
    { 
    } 
    catch (Exception ex) 
    { 
     Console.WriteLine("Unexpected Exception Occured: {0}", ex.Message); 
    } 
} 

Y un ejemplo de salida:

Input value '59' running... 
Input value '59' took 1711.8416ms 
Input value '14' running... 
Input value '14' took 90.9222ms 
Input value '43' running... 
Input value '43' took 902.7444ms 
Input value '22' running... 
Input value '22' took 231.5498ms 
Input value '50' running... 
Input value '50' took 1224.761ms 
Input value '27' running... 
Input value '27' took 351.3938ms 
Input value '5' running... 
Input value '5' took 9.8048ms 
Input value '28' running... 
Input value '28' took 377.8156ms 
Input value '26' running... 
Input value '26' took 325.4898ms 
Input value '46' running... 
Input value '46' took 1035.6526ms 
Execution time for input = 5 to 22 is greater than O(N^10) 
Execution time for input = 14 to 26 is roughly O(N^2) 
Execution time for input = 22 to 27 is roughly O(N^2) 
Execution time for input = 26 to 28 is roughly O(N^2) 
Execution time for input = 27 to 43 is roughly O(N^2) 
Execution time for input = 28 to 46 is roughly O(N^2) 
Execution time for input = 43 to 50 is roughly O(N^2) 
Execution time for input = 46 to 59 is roughly O(N^2) 
Fin. 

¿Qué muestra el método mágico es probable O(N^2) para las entradas dadas +/- 2% de la varianza

y otro resultado aquí:

Input value '0' took 0.7498ms 
Input value '1' took 0.3062ms 
Input value '2' took 0.5038ms 
Input value '3' took 4.9239ms 
Input value '4' took 14.2928ms 
Input value '5' took 29.9069ms 
Input value '6' took 55.4424ms 
Input value '7' took 91.6886ms 
Input value '8' took 140.5015ms 
Input value '9' took 204.5546ms 
Input value '10' took 285.4843ms 
Input value '11' took 385.7506ms 
Input value '12' took 506.8602ms 
Input value '13' took 650.7438ms 
Input value '14' took 819.8519ms 
Input value '15' took 1015.8124ms 
Execution time for input = 0 to 2 is greater than O(N^10) 
Execution time for input = 1 to 3 is greater than O(N^10) 
Execution time for input = 2 to 4 is greater than O(N^10) 
Execution time for input = 3 to 5 is greater than O(N^10) 
Execution time for input = 4 to 6 is greater than O(N^10) 
Execution time for input = 5 to 7 is greater than O(N^10) 
Execution time for input = 6 to 8 is greater than O(N^10) 
Execution time for input = 7 to 9 is greater than O(N^10) 
Execution time for input = 8 to 10 is roughly O(N^3) 
Execution time for input = 9 to 11 is roughly O(N^3) 
Execution time for input = 10 to 12 is roughly O(N^3) 
Execution time for input = 11 to 13 is roughly O(N^3) 
Execution time for input = 12 to 14 is roughly O(N^3) 
Execution time for input = 13 to 15 is roughly O(N^3) 

¿Qué muestra el método mágico es probable O(N^3) para la dada en pone +/- 2% de varianza

Así que es posible determinar programáticamente la complejidad de un algoritmo, debe asegurarse de no introducir algún trabajo adicional que lo haga más largo de lo que cree (como construir toda la entrada para la función antes de comenzar a temporizarla).

Además de esto, también debe recordar que tomará un tiempo significativo para probar una gran serie de valores posibles y devolver cuánto tiempo tomó, una prueba más realista es simplemente llamar a su función en un gran realista valor límite superior y determinar si el tiempo de respuesta es suficiente para su uso.

Es probable que solo necesite hacer esto si está realizando pruebas de caja negra sin código fuente (y no puede usar algo como Reflector para ver la fuente), o si debe probar a un PHB que los algoritmos codificados son tan rápidos como pueden (ignorando las mejoras en las constantes), como usted dice.