¿Se puede encontrar el valor de un algoritmo mediante programación mediante el análisis de sus perfs?

Question

Tenga en cuenta que no tengo un "problema" y no estoy buscando "otra forma de encontrar la gran O de mi algoritmo".

Lo que me gustaría saber es si sería posible escribir un programa al que se le pasarían puntos de datos que serían medidas de perforación de un algoritmo para varios tamaños de entrada: (n,time taken to solve problem for n) y eso determinaría la complejidad de tu algoritmo

Por ejemplo, aquí es lo que podría ser la entrada (que podría ser mucho más grande, en realidad es sólo un ejemplo, ese no es el punto de la pregunta):

36 000 took 16 ms 
    109 000 took 21 ms 
    327 000 took 68 ms 
    984 000 took 224 ms 
2 952 000 took 760 ms 
8 857 000 took 2305 ms 
26 571 000 took 7379 ms 
79 716 000 took 23336 ms 

El uso de este tipo de datos, es posible escribir un programa que diga si tenemos, por ejemplo, un O(n), log(n), n log(n) o n! algo?

Answer 1

Lo que está buscando es Curve fitting. Todos los algoritmos simples para este problema que conozco tratarán de encajar los puntos de datos en algún tipo de polinomio, pero sospecho que hay aquellos que también podrán diferenciar entre polinomios y no polinomios.

Answer 2

Creo que podría aproximarlo utilizando regresiones, pero no obtener resultados exactos. Esto se debe a que la mayoría de los algoritmos tienen un rendimiento diferente según la entrada (no solo el tamaño). Entonces, para entender esto completamente, necesitarías la fuente.

Answer 3

Puede usar el ajuste de curva (consulte @Max S.) para determinar la fórmula que describe sus datos. Sin embargo, esta es solo la mitad de la historia, ya que no hay forma de saber si los datos describen su algoritmo en toda su extensión.

Por ejemplo, su algoritmo puede presentar un comportamiento lineal para n < 1,000,000,000 y luego comenzar a comportarse de forma cuadrática. Si no tiene un punto de datos donde n> 1,000,000,000, entonces su programa de análisis no podrá darle una respuesta correcta.

Por lo tanto, para concluir puede hacerlo programáticamente, pero los resultados se limitarán a los puntos de datos en su muestra. Y no existe una forma algorítmica para determinar si la muestra cubre suficientemente todos los puntos "interesantes".

Answer 4

La mayoría de las grandes O suponen una máquina idealizada con memoria infinita con tiempo de acceso uniforme, sin influencia de otras aplicaciones, etc. Especialmente cuando se superan umbrales como tamaños de caché, tamaños de memoria principal (paginación entrada/salida del swapfile) puede tener una influencia significativa en el rendimiento. Entonces, lo que determina es cómo funciona el algoritmo en un mundo real y no es un tiempo de ejecución idealizado.

Answer 5

Si está intentando estimar empíricamente gran O, debe tener mucho cuidado para asegurarse de que está probando en una amplia gama de instancias de cada tamaño. Recuerde que big-O es peor caso noción. No es raro encontrar algoritmos que funcionan bien en casi todos los casos patológicos, pero son exactamente esos casos patológicos los que determinan el tiempo de O grande. Es decir, si te pierdes los casos patológicos en tu muestreo, podrías salir con la idea de que un algoritmo O (2^n) es O (n).

Si lo que realmente necesita es el gran O-tiempo, y no solo una idea del rendimiento promedio, entonces le recomiendo que lo pruebe analíticamente. Sin hacer eso, no puedes estar seguro de que no te hayas olvidado de ninguna información patológica.