¿Cómo calcular la complejidad exacta de un algoritmo?

Question

Sin recurrir a la notación asintótica, ¿es tedioso contar pasos la única forma de obtener la complejidad de tiempo de un algoritmo? Y sin contar el paso de cada línea de código, ¿podemos llegar a una representación en gran O de cualquier programa?

Detalles: tratando de descubrir la complejidad de varios algoritmos de análisis numérico para decidir cuál será el más adecuado para resolver un problema en particular. P. ej. - de entre el método Regula-Falsi o Newton-Rhapson para resolver eqns, la intención es evaluar la complejidad exacta de cada método y luego decidir (poniendo el valor de 'n' o cualquier argumento que exista) qué método es menos complejo.

Answer 1

La única manera --- no es la manera "fácil" o difícil pero la única manera razonable --- de encontrar la complejidad exacta de un algoritmo complicado es perfilarlo. Una implementación moderna de un algoritmo tiene una interacción compleja con bibliotecas numéricas y con la CPU y su unidad de coma flotante. Por ejemplo, el acceso a la memoria caché es mucho más rápido que el acceso a la memoria caché y, además, puede haber más de un nivel de caché. Los pasos de recuento son mucho más adecuados para la complejidad asintótica que usted dice que no es suficiente para su propósito.

Pero, si desea contar los pasos automáticamente, también hay formas de hacerlo. Puede agregar un comando de incremento de contador (como "bloof ++;" en C) a cada línea de código, y luego mostrar el valor al final.

También debe conocer la expresión de complejidad de tiempo más refinada, f (n) * (1 + o (1)), que también es útil para cálculos analíticos. Por ejemplo, n^2 + 2 * n + 7 se simplifica a n^2 * (1 + o (1)). Si el factor constante es lo que le molesta sobre la notación asintótica usual O (f (n)), este refinamiento es una forma de seguirlo y aún arrojar términos despreciables.

Answer 2

La 'manera fácil' es simularlo. Pruebe sus algoritmos con muchos valores de n y muchos datos diferentes, trace los resultados y luego haga coincidir la curva del gráfico con una ecuación.

Sus resultados pueden no ser estrictamente correctos y solo son tan válidos como su capacidad para generar buenos datos de prueba, pero en la mayoría de los casos esto funcionará.

Answer 3

E.g. - de entre el método Regula-Falsi o Newton-Rhapson para resolver eqns, la intención es evaluar la complejidad exacta de cada método y luego decidir (poniendo el valor de 'n' o cualquier argumento que exista) qué método es menos complejo.

No creo que sea posible responder esta pregunta en general para solucionadores no lineales. Puede obtener una cantidad exacta de cálculos por iteración, pero nunca sabrá en general cuántas iteraciones llevará cada solucionador converger. Hay otras complicaciones como necesitar el Jacobiano para Newton, lo que podría dificultar aún más la complejidad de la computación.

En resumen, el solucionador no lineal más eficiente siempre depende del problema que está resolviendo. Si la variedad de problemas que está resolviendo es muy limitada, hacer muchos experimentos con diferentes solucionadores y medir el número de iteraciones y el tiempo de CPU probablemente le brinden más información útil.