Creo que en realidad es muy difícil , por la sencilla razón de que la mayoría de las veces no tienes idea de lo que realmente significa “datos promedio”.
La definición trivialmente significaría “el rendimiento promedio sobre todas las entradas posibles ” … pero hay advertencias obvias:
- la mayoría de las veces, esto es imposible de calcular en la práctica debido al número astronómico de “todas las entradas posibles”, incluso para tamaños de datos modestos. Mire el paquete de contenedores “good’ol”: se supone que los tamaños de los artículos son reales (en lugar de discretos), por lo que, estrictamente hablando, termina con una infinidad de datos posibles diferentes
- definitivamente no está claro (incluso es dudoso ) que todos los datos posibles se enviarían alguna vez en la vida real : con qué frecuencia clasifica una matriz donde la mitad de los valores son iguales o la mayoría se clasifican en orden inverso, con qué frecuencia se enfrenta ¿Un TSP (Problema de vendedor ambulante) donde la mitad de las distancias / costos por pares son iguales? Básicamente nunca lo adivinaría.
Supongo que un enfoque defendible sería alimentar el algoritmo con un millón de instancias completamente aleatorias y observar el tiempo de ejecución, luego obtener el promedio de (¡lo que supongo que sería!) El gaussiano resultante.
- Cómo ordenar la matriz de tipos primitivos en orden descendente en Java
- Estoy buscando algunas clases que me darían consejos sobre el enfoque. ¿Debo tomar el diseño del sistema, el algoritmo o la preparación de la estructura de datos?
- ¿En qué punto Watson podrá crear sus propios algoritmos?
- ¿Se requiere un buen conocimiento de la estructura de datos y algoritmos para saltar a la codificación competitiva?
- ¿Cuáles son los mejores sitios web con problemas de práctica de algoritmos?
Pero si eso reflejaría los datos que normalmente los alimentaría en la vida real , probablemente sería bastante incierto.
