He leído sobre grandes notación para la complejidad del tiempo y para contar funciones como la de los números primos. Recientemente en StackOverflow leí:
El problema de definir cuánto tarda en ejecutarse un algoritmo es que, por lo general, no puede dar una respuesta en milisegundos porque depende de la máquina, y no puede dar una respuesta en ciclos de reloj o como un recuento de operaciones porque eso sería demasiado específico para datos particulares para ser útil.
https://stackoverflow.com/questions/11806021/how-does-one-calculate-the-runtime-of-an-algorithm
Mi pregunta es, si consideramos un algoritmo que se ejecuta en una complejidad de tiempo conocida (polinomio, lineal, etc.) en una máquina cuyos parámetros se conocen, ¿cómo podemos calcular el tiempo de ejecución en segundos? Esencialmente, ¿cómo se puede traducir la complejidad del tiempo a tiempo real para una máquina determinada?
Pregunto porque he visto instancias donde la gente ha dicho el algoritmo tomará Hora de correr.
Por lo que entiendo después de leer la página de wikipedia sobre la complejidad del tiempo, creo que es el valor polinomial o la cantidad de cálculos dividido por la cantidad de cálculos que una máquina determinada puede procesar por unidad de tiempo. ¿Es esto correcto? ¿Hay una respuesta general?
Básicamente, el concepto de complejidad temporal surgió cuando la gente quería saber la dependencia temporal de un algoritmo en el tamaño de entrada, pero nunca tuvo la intención de calcular el tiempo de ejecución exacto del algoritmo. Como depende de la cantidad de factores, como el procesador, el sistema operativo, los procesos y muchos más..., que no se pueden contabilizar en notación O grande, ya que ignora todos los términos de grado inferior.
Carátula Caratula de SmileyCraft