¿Debería uno probar la complejidad algorítmica? ¿Si es así, cómo?

La complejidad algorítmica es una construcción teórica y, como tal, se "prueba" con un lápiz y papel. No puede probarse de manera útil mecánicamente.

El rendimiento absoluto puede se puede probar mecánicamente y puede realizar pruebas unitarias útiles. Si el rendimiento es importante, entonces puede especificar un umbral: "esta consulta no debería tardar más de 50 ms en ejecutarse en 10 números ⁶ , y no más de 60 ms en 10 números ⁷ . " Que puedas construir una prueba de unidad para.

Al usuario final no le importa si su algoritmo es lineal o logarítmico; les importa si su IU sigue respondiendo de manera instantánea, incluso cuando tienen un año de datos en la aplicación.

Aunque no estoy seguro de que esta herramienta sea particularmente útil para las pruebas unitarias, el documento La "complejidad computacional empírica" de Goldsmith, Aiken y Wilkerson describe un método para instrumentar código y observar su comportamiento dinámico en un conjunto de varias entradas para derivar empíricamente su complejidad asintótica. El programa descrito en el documento es de código abierto y está disponible aquí .

Espero que esto ayude!

Lo principal es probarlo con big data y ver si demora demasiado.

En mi experiencia de ajuste de rendimiento, como en este ejemplo , lo que sucede es que si algún algoritmo es (por ejemplo) O (n ^ 2) puede estar bien siempre que el porcentaje de tiempo que toma nunca llegue al radar.

Sin embargo, cuando se le da un conjunto de datos de un tamaño que podría no verse pero una vez al año, la fracción del tiempo total absorbido por ese algoritmo puede llegar a ser catastróficamente dominante.

Si puedes hacer que eso suceda en las pruebas, eso es algo muy bueno, porque es sumamente fácil encontrar el problema, como si se tratara de un bucle infinito real.

No creo que lo que quieras hacer sea una prueba unitaria.

AFAIK, la prueba unitaria es solo para asegurarse de que el código hace lo que debe hacer y no se centra en el rendimiento.

  

De Wikipedia : no se puede esperar que las pruebas detecten todos los errores en el programa: es imposible evaluar cada ruta de ejecución En todos menos los programas más triviales. Lo mismo es cierto para la prueba de la unidad. Además, la prueba de unidad por definición solo prueba la funcionalidad de las unidades en sí. Por lo tanto, no detectará errores de integración ni errores más amplios a nivel del sistema (como las funciones realizadas en varias unidades o áreas de prueba no funcionales como el rendimiento). la prueba de la unidad se debe realizar junto con otras actividades de prueba de software . Como todas las formas de prueba de software, las pruebas unitarias solo pueden mostrar la presencia de errores; No pueden mostrar la ausencia de errores.

Hay otros tipos de herramientas y patrones para medir el rendimiento. Uno de los que puedo recordar ahora es que pruebas de aceptación se centran en los requisitos no funcionales.

Hay algunos otros como pruebas de rendimiento (que utiliza pruebas de estrés, pruebas de carga, etc.).

También podría usar algunas herramientas de estrés junto con una herramienta de compilación (ant, estudio de creación automatizado) como parte de los pasos de implementación (eso es lo que hago).

Así que la respuesta corta es no, no debes preocuparte por eso cuando la unidad prueba un código.

Pasar en el comparador y tener que hacer un seguimiento del número de veces que se llama funcionará con propósitos simples, como verificar que el número de comparaciones al realizar una búsqueda en una entrada fija (por ejemplo, new int[] { 1,2,3, ... , 1024 } ) se mantenga por debajo de 10 Eso al menos dejará en claro sus intenciones sobre cómo se supone que se comporta el algoritmo.

No creo que las pruebas unitarias sean el camino correcto para verificar que su algoritmo es O (log n); eso requeriría una gran cantidad de generación de datos aleatorios, algunos ajustes de curvas y probablemente estadísticas complejas para determinar si un conjunto de puntos de datos se ajusta al tiempo de ejecución esperado. (Para este algoritmo es probable que sea factible, pero si empiezas a clasificar, etc., será difícil llegar repetidamente a los peores escenarios).